Maximum Subarray

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

[tabby title=”Solution”]

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.

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`

 i nums[i] action described max_here max_so_far 1 1 `sum = max_here + nums[1]`, which is: `sum = -2 + 1 = -1` which is smaller than `nums[1]` so `max_here = nums[1] = 1` (line 10 in the code snipped below) and since `max_here > max_so_far`,  `max_so_far = max_here =1` (line 11) 1 1 2 -3 `sum = max_here + nums[2]` which is: `sum = 1 + (-3) = - 2` which is bigger than `nums[2]` which is -3 so `max_here = sum = -2`But `max_here` is smaller than `max_so_far` so `max_so_far` stays equal to 1 -2 1 3 4 `sum = -2 + 4 = 2` which is < than 4 so  `max_here = nums[4] = 4` which is > `max_so_far` so `max_so_far = max_here = 4` 4 4 4 -1 `sum = 4 - 1 = 3` > – 1 so `max_here = sum = 3` 3 4 5 2 `sum = 3 + 2 = 5` which is > than `nums[5] = 2` so `max_here = max_so_far = sum = 5` 5 5 6 1 `sum = 5 + 1 = 6` which is > than `nums[6] = 1` so `max_here = max_so_far = sum = 6` 6 6 7 -5 `sum = 6 + (-5) = 1` which is > than `nums[7] = -5` so `max_here = 1` 1 6 8 4 `sum = 1 + 4 = 5` which is > than `nums[8] = 4` so `max_here = 5` but `max_here < max_so_far` so `max_so_far` stays the same: 6 which is the maximum sum here. 5 6

```/**
* @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;
};```

[tabbyending]