Java O(n) solution with approach explained in theory


#1

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);
    
}

}