miércoles, 5 de marzo de 2008

Maximum subarray (java implementation)

You're given an array containing both positive and negative integers and required to find the subarray with the maximum sum.

This is an interesting problem, I read that the solution was given in 1977 in less than a minute, so I took the original algorithm for the article and I implemented with Java, enjoy it!

    public static void main(String[] args)
    {
        int[] offset = new int[2];
        int[] x = { 31, -41, 59, 26, -53, 58, 97, -93, -23, 18 };
        int n = x.length;
        int maxsofar = 0;
        for (int i = 0; i < n; i++)
            for (int j = i; j < n; j++)
            {
                int sum = 0;
                for (int k = i; k <= j; k++)
                    sum += x[k];
                /* sum is sum of x[i..j] */
                if (sum > maxsofar)
                {
                    offset[0] = i;
                    offset[1] = j;
                    maxsofar = sum;
                }
            }
        System.out.println("Subarray [" + offset[0] + "..." + offset[1]
                + "] = " + maxsofar);
    }

No hay comentarios.: