Converting pseudocode for max subarray into working Java code I have been tasked with converting some pseudocode to working Java code and I would like someone to review my code for correctness.

The pseudocode is as follows:



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 &gt; m then
            m ← s
return m


My code is as follows:



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 &lt; 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 &lt; array.length; j++)
        {
            for (int k = j; k &lt; array.length; k++)
            {
                //s = S_k - S_j-1
                int s = S[k] - S[j - 1];
                //if s &gt; m, m &lt;- s
                if (s &gt; max)
                {
                    max = s;
                }
            }
        }
        return max;
    }//end maxSubFaster


The algorithm seems to work, but any pointers or corrections would be great!
Your translation is pretty faithful to the already low-level pseudocode but you could:


The pseudocode talks about an array of numbers and not integers, but that is just a simple type change, and doesn't affect the logic at all
copy array.length into variable n near the top, and use n throughout as the original code does,
remove the initial filling of S with 0's, since your first loop will overwrite them anyway (and that was not in the original code)
change max to m, and array to A, but you could argue this makes your code more readable


This probably isn't the point of the exercise, but it is possible to solve this problem with a single loop that scans through the array just once, for a more efficient solution.