Maximum subarray sum🤖

Subarray questions require looping through an array but with some extra logic/conditions which can make them challenging. However, I think this solution can be straightforward to understand as there are only a couple of conditions.

This problem asks to find the biggest sum of consecutive numbers in the array:

let nums = [ -3, 1, -4, 1, 2, 1]
// solution -> 4 ( from 1,2,1 subarray)

The approach, in this case, involves accumulating the sum of the numbers in the previous element, while we check for the highest sum between the new sum that includes the current element and the previous sum. So the first subarray sum would only be the first value of the array, which is used to accumulate the sum of the next elements.

sum = nums[0]

In the base case, there are no more elements to loop through so we just return the first element by skipping the loop.

But if there are more elements to loop over we start with the second element (index 1) until the end of the array. Starting at index 1 allows comparing the current element to the previous element from the first loop.

if (nums[i - 1] > 0) { 
// only if the previous accumulation sum (previous element) is positive
  nums[i] += nums[i - 1]; // accumulate current element by adding last to current
}

After we accumulate the sum of the previous elements in nums[i] and nums[i-1], we can compare the current sum (nums[i]) to the highest sum (sum) so far.

sum = Math.max(nums[i], sum)

In the first loop sum will be the first element of the array and after it will become the highest sum we found so far.

The whole algorithm:

const maxSubArray = (nums) => {
    let sum = nums[0];

    for (let i = 1; i < nums.length; i++) { 
// starts at index one to compare and acculumate 

        if (nums[i - 1] > 0) { 
// if the accumulation sum is positive
            nums[i] += nums[i - 1]; 
// accumulate current element by adding current to last
        }

        sum = Math.max(nums[i], sum); 
        // save highest number either current sum of previous higher sum
    }
    return sum;
};

To review, we loop over the array and check to see if the previously accumulated sum is positive and if true add the current element. Last we compare the current sum to the highest sum so far with Math.max after we iterated over the whole array we return the answer: sum.

Feel free to reach out with any thoughts/ideas!

At LinkedIn or twitter