Algorithm MaxsubFaster(A):
Input: An n-element array A of numbers, indexed from 1 to n.
Output: The maximum subarray sum of array A.
S0 ← 0 // the initial prefix sum
for i ← 1 to n do
    Si ← Si−1 + A[i]
m ← 0 // the maximum found so far
for j ← 1 to n do
    for k ← j to n do
        s = Sk − Sj−1
        if s > m then
            m ← s
return m

public static int maxSubFaster(int[] array)
    {
        Integer S[] = new Integer[array.length];
        Arrays.fill(S,0);

        //initial prefix sum
        S[0] = 0;
        for (int i = 1; i < array.length; i++)
        {
            //S_i = S_i-1 + A[i]
            S[i] = S[i - 1] + array[i];
        }
        //maximum found so far
        int max = 0;
        for (int j = 1; j < array.length; j++)
        {
            for (int k = j; k < array.length; k++)
            {
                //s = S_k - S_j-1
                int s = S[k] - S[j - 1];
                //if s > m, m <- s
                if (s > max)
                {
                    max = s;
                }
            }
        }
        return max;
    }//end maxSubFaster