DEV Community is a community of 787,570 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

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;
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;
let maxSum = A;
for(let i=1;i<A.length;i++){
sum = Math.max(sum+A[i],A[i]);
maxSum = Math.max(maxSum,sum);
}
return maxSum;
};