package analysis;

import java.util.Random;

public class MaxSubTest {

    static private int seqStart = 0;
    static private int seqEnd = -1;

    /**
     * Cubic maximum contiguous subsequence sum algorithm. seqStart and seqEnd
     * represent the actual best sequence.
     */
    public static int maxSubSum3(int[] a) {
        int maxSum = 0;

        for (int i = 0; i < a.length; i++)
            for (int j = i; j < a.length; j++) {
                int thisSum = 0;

                for (int k = i; k <= j; k++)
                    thisSum += a[k];

                if (thisSum > maxSum) {
                    maxSum = thisSum;
                    seqStart = i;
                    seqEnd = j;
                }
            }

        return maxSum;
    }

    /**
     * Quadratic maximum contiguous subsequence sum algorithm. seqStart and
     * seqEnd represent the actual best sequence.
     */
    public static int maxSubSum2(int[] a) {
        int maxSum = 0;

        for (int i = 0; i < a.length; i++) {
            int thisSum = 0;
            for (int j = i; j < a.length; j++) {
                thisSum += a[j];

                if (thisSum > maxSum) {
                    maxSum = thisSum;
                    seqStart = i;
                    seqEnd = j;
                }
            }
        }

        return maxSum;
    }

    /**
     * Linear-time maximum contiguous subsequence sum algorithm. seqStart and
     * seqEnd represent the actual best sequence.
     */
    public static int maxSubSum1(int[] a) {
        int maxSum = 0;
        int thisSum = 0;

        for (int i = 0, j = 0; j < a.length; j++) {
            thisSum += a[j];

            if (thisSum > maxSum) {
                maxSum = thisSum;
                seqStart = i;
                seqEnd = j;
            } else if (thisSum < 0) {
                i = j + 1;
                thisSum = 0;
            }
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] a = new int[Integer.parseInt(args[0])];
        Random rand = new Random();

        for (int i = 0; i < a.length; ++i) {
            a[i] = rand.nextInt() % 10;
        }

        int maxSum;

        maxSum = maxSubSum1(a);
        System.out.println("\nMax sum is " + maxSum + "; it goes" + " from "
                + seqStart + " to " + seqEnd);
        System.out.flush();

        maxSum = maxSubSum2(a);
        System.out.println("\nMax sum is " + maxSum + "; it goes" + " from "
                + seqStart + " to " + seqEnd);
        System.out.flush();

        maxSum = maxSubSum3(a);
        System.out.println("\nMax sum is " + maxSum + "; it goes" + " from "
                + seqStart + " to " + seqEnd);
        System.out.flush();
    }
}