June 17, 2025 – The Rails Drop

Welcome to my new series where I combine the power of Ruby with the discipline of Test-Driven Development (TDD) to tackle popular algorithm problems from LeetCode! 🧑‍💻💎 Whether you’re a Ruby enthusiast looking to sharpen your problem-solving skills, or a developer curious about how TDD can transform the way you approach coding challenges, you’re in the right place.

🎲 Episode 5: Maximum Subarray

#Given an integer array nums, find the subarray with the largest #sum, and return its sum.

#Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
#Explanation: The subarray [4,-1,2,1] has the largest sum 6.

#Example 2:
Input: nums = [1]
Output: 1
#Explanation: The subarray [1] has the largest sum 1.

#Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
#Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
 
#Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
 
#Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

🔧 Setting up the TDD environment

mkdir maximum_subarray
touch maximum_subarray/maximum_subarray.rb
touch maximum_subarray/test_maximum_subarray.rb

❌ Red: Writing the failing test

Test File:

# ❌ Fail
# frozen_string_literal: true

require 'minitest/autorun'
require_relative 'maximum_subarray'
#################################
## Example 1:
# Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
# ..........
#################################
class TestMaximumSubarray < Minitest::Test
  def setup
    ####
  end

  def test_empty_array
    assert_equal 'Provide non-empty array', Subarray.new([]).max
  end
end

Source Code:

# frozen_string_literal: true

#######################################
# Given an integer array nums, find the subarray with the largest #sum, and return its sum.

# Example 1:
# Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
# Output: 6
# Explanation: The subarray [4,-1,2,1] has the largest sum 6.

# Example 2:
# Input: nums = [1]
# Output: 1
# Explanation: The subarray [1] has the largest sum 1.

# Example 3:
# Input: nums = [5,4,-1,7,8]
# Output: 23
# Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

# Constraints:
# 1 <= nums.length <= 105
# -104 <= nums[i] <= 104

# Follow up: If you have figured out the O(n) solution, try coding another solution using
# the divide and conquer approach, which is more subtle.
#######################################

✗ ruby maximum_subarray/test_maximum_subarray.rb
Run options: --seed 18237

# Running:
E.

Finished in 0.000404s, 4950.4950 runs/s, 0.0000 assertions/s.

  1) Error:
TestMaximumSubarray#test_empty_array:
NameError: uninitialized constant TestMaximumSubarray::Subarray
    maximum_subarray/test_maximum_subarray.rb:31:in 'TestMaximumSubarray#test_empty_array'

2 runs, 0 assertions, 0 failures, 1 errors, 0 skips

✅ Green: Making it pass

# frozen_string_literal: true

require 'minitest/autorun'
require_relative 'maximum_subarray'
#################################
## Example 1:
# ..........
#################################
class TestMaximumSubarray < Minitest::Test
  def setup
    ####
  end

  def test_empty_array
    assert_equal 'Provide non-empty array', Subarray.new([]).max
  end

  def test_array_with_length_one
    assert_equal 1, Subarray.new([1]).max
  end
end

✗ ruby maximum_subarray/test_maximum_subarray.rb
Run options: --seed 52896

# Running:
.

Finished in 0.000354s, 2824.8588 runs/s, 2824.8588 assertions/s.
1 runs, 1 assertions, 0 failures, 0 errors, 0 skips

# Pass ✅ 
# frozen_string_literal: true

#######################################
# Given an integer array nums, find the subarray with the largest #sum, and return its sum.

# Example 1:
# ........
#######################################
class Subarray
  def initialize(numbers)
    @numbers = numbers
  end

  def max
    return 'Provide non-empty array' if @numbers.empty?

    @numbers.first if @numbers.length == 1
  end
end

………………………………………………….⤵ …………………………………………………………..

# Full Solution 1 ✅ 
# frozen_string_literal: true

#######################################
# Given an integer array nums, find the subarray with the largest #sum, and return its sum.

# Example 1:
# .........
#
#   Ex: Subarray.new([4, -1, 2, 1]).max_sum
#######################################
class Subarray
  def initialize(numbers)
    @numbers = numbers
  end

  def max_sum
    return 'Provide non-empty array' if @numbers.empty?

    return @numbers.first if @numbers.length == 1

    maximum_sum = @numbers.first
    # do array right side scan
    @numbers.each_with_index do |num, i|
      current_sum = num # calculate from current number
      right_side_numbers = @numbers[(i + 1)..]
      is_last_number_of_array = right_side_numbers.empty?
      maximum_sum = current_sum if is_last_number_of_array && current_sum > maximum_sum

      right_side_numbers.each do |num_right|
        current_sum += num_right
        maximum_sum = current_sum if current_sum > maximum_sum
      end
    end

    maximum_sum
  end
end

⏳ Finding the Time Complexity

Looking at our max_sum algorithm, let’s analyze the time and space complexity:

Time Complexity: O(n²)

The algorithm has two nested loops:

Outer loop: @numbers.each_with_index runs n times (where n = array length)
Inner loop: right_side_numbers.each runs (n-i-1) times for each position i

The total number of operations is:

i=0: inner loop runs (n-1) times
i=1: inner loop runs (n-2) times
i=2: inner loop runs (n-3) times
…
i=n-1: inner loop runs 0 times

Total iterations = (n-1) + (n-2) + (n-3) + … + 1 + 0 = n(n-1)/2 = O(n²)

Space Complexity: O(n)

The space usage comes from:

Constant space: maximum_sum, current_sum, is_last_number_of_array → O(1)
Array slicing: @numbers[(i + 1)..] creates a new array slice each iteration → O(n)

The key space consumer is the line:

right_side_numbers = @numbers[(i + 1)..]

This creates a new array slice for each position. The largest slice (when i=0) has size (n-1), so the space complexity is O(n).

Summary:

Time Complexity: O(n²) – quadratic due to nested loops
Space Complexity: O(n) – linear due to array slicing

This is a brute force approach that checks all possible contiguous subarrays by starting from each position and extending to the right.

♻️ Refactor: Optimizing the solution

# Final - Solution 2 ✅ 
# Optimized O(n) time, O(1) space solution

# frozen_string_literal: true

#######################################
# Given an integer array nums, find the subarray with the largest #sum, and return its sum.

# Example 1:
# Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
# Output: 6
# Explanation: The subarray [4,-1,2,1] has the largest sum 6.

# Example 2:
# Input: nums = [1]
# Output: 1
# Explanation: The subarray [1] has the largest sum 1.

# Example 3:
# Input: nums = [5,4,-1,7,8]
# Output: 23
# Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

# Constraints:
# 1 <= nums.length <= 105
# -104 <= nums[i] <= 104

# Follow up: If you have figured out the O(n) solution, try coding another solution using
# the divide and conquer approach, which is more subtle.
#
#   Ex: Subarray.new([4, -1, 2, 1]).max_sum
#######################################
class Subarray
  def initialize(numbers)
    @numbers = numbers
  end

  def max_sum
    return 'Provide non-empty array' if @numbers.empty?

    return @numbers.first if @numbers.length == 1

    max_sum = @numbers.first
    inherit_sum = @numbers.first
    @numbers[1..].each do |num|
      inherit_sum_add_num = inherit_sum + num
      # if current num is greater than inherited sum break the loop and start from current num
      inherit_sum = num > inherit_sum_add_num ? num : inherit_sum_add_num
      # preserve highest of this inherited sum for each element iteration
      max_sum = inherit_sum > max_sum ? inherit_sum : max_sum
    end
    max_sum
  end
end

LeetCode Submission:

# @param {Integer[]} nums
# @return {Integer}
# [4, -1, 2, 1]
# [-2, 1, -3, 4]
def max_sub_array(nums)
    return 'Provide non-empty array' if nums.empty?

    return nums.first if nums.length == 1

    max_sum = nums.first
    inherit_sum = nums.first
    nums[1..].each do |num|
        inherit_sum_add_num = inherit_sum + num
        # if current num is greater than inherited sum break the loop and start from current num
        inherit_sum = num > inherit_sum_add_num ? num : inherit_sum_add_num
        # preserve highest of this inherited sum for each element iteration
        max_sum = inherit_sum > max_sum ? inherit_sum : max_sum
    end
    max_sum
end