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

## Discussion (0)