Approach:
we store curmax as the first element in the array and
max is to store the largest curmax value throughout the loop.
First we traverse through the array…
inside the loop:
curmax = maximum of curmax+A[i] and A[i].
We also make note of the largest
curmax in max variable…and return the larger of max and curmax
Actual code:
public class Solution {
// DO NOT MODIFY THE ARGUMENTS WITH “final” PREFIX. IT IS READ ONLY
public int maxSubArray(final int[] A) {
int curmax = A[0];
int max = A[0];
for(int i=1;i<A.length;i++)
{
curmax = Math.max(curmax+A[i],A[i]);
max = Math.max(curmax,max);
}
return Math.max(curmax,max);
}
}