Find the maximum subarray with Ruby approach

Question Overview

You are given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example

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

Assume nums.length=1, the largest sum will be nums[0].

Assume num.length=2, the largest num will be either num[0] or num[0]+num[1], we can use max method to determine which one is bigger. If the nums[0] < nums[0] + nums[1], replace the largest sum with the sum of the first two elements. store the value of the largest sum to compare with the sum of the first three element, and so on and so forth.

I started by defining two variables, largest_sum and current.

largest_sum = nums[0]
current = 0

Next, loop through the array with each enumerable.

nums.each {|n| largest_sum = [largest_sum, current = [n, current+n].max].max}

The general picture here is to compare the two variables largest_sum with current, if current is bigger than largest_num, largest_num = current. Let’s break it down:

Take the array [-2,1,-3,4,-1,2,1,-5,4] as example.

First looping

current = [n, current+n].max 
#current = [-2,0-2].max
#current => -2
largest_sum = [largest_sum, current].max
#largest_sum = [-2,-2].max
#largest_num =>-2

After the first looping current, current is equal to the largest_num.

Second looping:

current = [n, current+n].max 
#current = [1, -2+1].max
#current => 1
largest_sum = [largest_sum, current].max
#largest_num = [-2,1].max 
#largest_num = 1

The first element is -2, sum of the first two element is -1, and the second element is 1 which is the largest amount the three. During the second looping, the second element first compare with the sum of the first element, the bigger one continue compare with the largest_num from previous looping. The variable current is changing with the block n.

The Final Code

def max_sub_array(nums)
   largest_sum,current = nums[0], 0
   nums.each{|x| largest_sum = [largest_sum, current=[x, current + x].max].max}
   largest_sum
end

Closing Note

This is an easy LeetCode array question. There are more ways to tackle this question, such as recursion with while loop. Thank you for reading, and happy coding.