Maximum Subarray, Kadane's algorithm

Question: Given an array, find the maximum subarray sum.

Eg: For given array : [-2,1,-3,4,-1,2,1,-5,4]
output : 6 for subarray [4,-1,2,1]

Brute force: O(n^2)

Brute force solution would be to go generate all possible subarray and find the maximum subarray.

var maxSubArray = function(nums) {
    if(nums.length == 0) return 0;
    let max = nums[0];
    for(let i=0;i<nums.length;i++){
        let sum = 0;
        for(let j=i;j<nums.length;j++){
            sum+=nums[j];
            if(max<sum) max = sum;
        }
    }
    return max;
};

Now let's observe and find patterns that might help us optimize our solution.

For an Array A let's consider the following observations
If for subarray Sum(A[i,....,j-1]) < A[j], then we know that there's no need to calculate Sum(A[i+1....,j-1]) again since it will definitely be less than A[i].

So based on this, if we come across a situation where current element is greater than sum of previous elements, then we shall start a new subarray from the current subarray.

Let's understand this :

So as you can see here,
1 > we maintain two containers, sum and maxSum, we keep on adding elements to sum and compare it with maxSum, and change maxSum only if sum>maxSum.
2 > we change sum when the current element is greater than sum.

this approach improve our time from O(n^2) to O(n).

code:

var maxSubArray = function(A) {
    let sum = A[0];
    let maxSum = A[0];
    for(let i=1;i<A.length;i++){
        sum = Math.max(sum+A[i],A[i]);
        maxSum = Math.max(maxSum,sum);
    }
    return maxSum;
};

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/tree/master/problems