Maximum Sub-array in Ruby

This is meaningful when there are some negative numbers in the array. Otherwise, there is no need to use a recursive function. We can get the sum of all items in the array.

If all items are positive then no need to make complex calculations to get the addition of the numbers in the array.

array = [2, 5, 6, 2, 1, 7, 8, 12, 4, 20, 7, 9, 10]
# result is array.sum 
> 93

If all items are negative then the maximum sub-array will be 0

array = [-3, -5, -5, -3, -2, -7, -1, -9, -6, -12]
# result is sum[] = 0
> 0

On the other hand, if there a both positive and negative numbers in the array we can try to find the maximum sub-array of this array with a recursive function.

class MaxSubArrayOptimized
  def initialize(prices)
    @prices = prices
    @global_max = 0
    local_max = 0
    for i in 0..prices.length - 1
      local_max = if i == 0
                    @prices[0]
                  else
                    [@prices[i], @prices[i] + local_max].max
                  end
      @global_max = [@global_max, local_max].max
    end 
  end
  
  def max_sub_array()
    @global_max
  end
end

msa = MaxSubArrayOptimized.new([-3, -5, 5, -3, 2, 7, -1, -9, 6, -12])
puts msa.max_sub_array
# 11

This optimized version efficiently identifies the maximum sub-array, demonstrating remarkable speed even when tackling more intricate variations. For instance:

input = [1] * 10000
for i in 0..9
  msa = MaxSubArrayOptimized.new(input)
  puts (msa.max_sub_array)
end

#result will be nine times 10000
# 10000
# 10000
# 10000
# 10000
# 10000
# 10000
# 10000
# 10000
# 10000
# 10000

Also, there is an alternative solution for returning a negative maximum sub-array.

# @param {Integer[]} nums
# @return {Integer}
def max_sub_array(nums)
    @nums = nums
    @global_max = 0
    local_max = 0

    for i in 0..@nums.length - 1
        local_max = if i == 0
                        @nums[i]
                        @global_max = @nums[i]
                    else
                        [@nums[i], @nums[i] + local_max].max
                    end
        @global_max = [@global_max, local_max].max
    end

    @global_max
end

puts max_sub_array([-1])
# -1

puts max_sub_array([-3])
# -3

Thanks for reading.

#Maximum Sub Array #Ruby #Recursive Functions #Dynamic Programming #Algorithms #Ruby on Rails