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.

This problem was taken from Leetcode

The solution:

Brut force.

The straight forward solution could be to iterate through all elements in the array and calculate the subarray values and compare them.

In the example above[-2,1,-3,4,-1,2,1,-5,4] we will do:

starting index: 1
-2 = -2
-2, 1 = -1
-2, 1, -3 = -4
-2, 1, -3, 4 = 0
-2, 1, -3, 4, -1 = -1
-2, 1, -3, 4, -1, 2 = 1
-2, 1, -3, 4, -1, 2, 1 = 2
-2, 1, -3, 4, -1, 2, 1, -5 = -3
-2, 1, -3, 4, -1, 2, 1, -5, 4 = 1

starting index: 2
1 = 1
1, -3 = -2
1, -3, 4 = 2
1, -3, 4, -1 = 1
1, -3, 4, -1, 2 = 3
1, -3, 4, -1, 2, 1 = 4
1, -3, 4, -1, 2, 1, -5 = -1
1, -3, 4, -1, 2, 1, -5, 4 = 3

starting index: 3
-3 = -3
-3, 4 = 1
-3, 4, -1 = 0
-3, 4, -1, 2 = 2
-3, 4, -1, 2, 1 = 3
-3, 4, -1, 2, 1, -5 = -2
-3, 4, -1, 2, 1, -5, 4 = 2

starting index: 4
4 = 4
4, -1 = 3
4, -1, 2 = 5
4, -1, 2, 1 = 6
4, -1, 2, 1, -5 = 1
4, -1, 2, 1, -5, 4 = 5

… and so on till the last element in the array.

So the winner clearly is 4, -1, 2, 1 = 6, but this approach will take a lot of repetitions. Interestingly there is a linear solution called: Kadane’s algorithm.

Using Kadene’s algorithm.

The basic idea of this algorithm is to break the array into a sets of mutually exclusive sets, calculate their sums and find the largest one.

First let’s look closely of what we are doing to find the maximum sum using brut force. We are splitting the array to a sets of all possible contiguous sub arrays and we calculate their sum. This means that:
– if the array contains only negative values we don’t really need to split the array cause the answer will be the largest value in the array. i.e. [-1,-5,-3] = -1 (the one close to 0)
– if this is a mixed array with negative and positive values the max sum of contiguous sub array will be > 0 so we could ignore any case where the sum is negative.

This way we could iterate through each element of the array nums[i]  where i is the index of the element in the array (starting with the first one nums[0]), and calculate the sum (let’s call it max_here = max_here + nums[i] ).
If we get a negative result we already know for sure that this is not what we are looking for and we set up max_here to the next element in the array max_here = nums[i]

So in the example above: [-2,1,-3,4,-1,2,1,-5,4]
We are starting by setting up both params to the first element in the array: max_here =max_so_far = nums[0] . We are going to use max_so_far to store the maximum sum discovered so far, and max_here to calculate the maximum sum so far. Once again if the max_sum is negative, we just set it up to be equal to the next element in the array nums[i] so on the next iteration max_sum = nums[i-1] + nums[i]

Starting with setting up max_here = max_so_far = nums[0] = -2

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    var max_here = max_so_far = nums[0];
    

    for(var i=1;i < nums.length; i ++) {
        max_here = Math.max(max_here + nums[i], nums[i]);
        max_so_far = Math.max(max_so_far, max_here);
    }    

    return max_so_far;
};