import java.util.ArrayList;

/**
 * @author Sean Allred
 * @author Molly Domino
 *
 *         Tests the Maximum Contiguous Subsequence Sum Algorithms N^3 and N^2
 */
public class driver {

    public static final long MAX_LONG = 9223372036854775807L;

    /**
     * O(n^3) algorithm. Takes every possible subset, sums, and returns the maximum
     * sum to the user
     *
     * @param arr
     *            the array to operate on
     * @return the maximum contiguous subset sum
     */
    private static int subSum_N3(int arr[]) {
        int maxSum = 0;

        for (int startElement = 0; startElement < arr.length - 1; startElement++) {
            for (int endElement = startElement; endElement < arr.length; endElement++) {
                int thisSum = 0;
                for (int thisElementIndex = startElement; thisElementIndex <= endElement; thisElementIndex++) {
                    thisSum += arr[thisElementIndex];
                }
                // update max
                if (thisSum > maxSum)
                    maxSum = thisSum;
            }
        }
        return maxSum;
    }

    /**
     * O(n^2) algorithm. Also takes every possible subset, but sums common subsets
     * only once
     *
     * @param arr
     *            the array to operate on
     * @return the maximum contiguous subset sum
     */
    private static int subSum_N2(int arr[]) {

        int maxSum = 0, thisSum = 0;

        for (int startElement = 0; startElement < arr.length; startElement++) {
            thisSum = 0;
            for (int endElement = startElement; endElement < arr.length; endElement++) {
                thisSum += arr[endElement];
                // update max
                if (thisSum > maxSum)
                    maxSum = thisSum;
            }
        }
        return maxSum;

    }

    /**
     * O(n) algorithm. Baws.
     *
     * @param arr the array to operate on
     * @return the maximum contiguous subsequence sum
     */
    private static int subSum_N1(int arr[]) {
        int maxSum = 0, thisSum = 0, endElement = 0;
        // Cycle through all possible end indexes.
        for (endElement = 0; endElement < arr.length; endElement++) {
            thisSum += arr[endElement]; // No need to re-add all values.
            if (thisSum > maxSum) {
                maxSum = thisSum;
            } else if (thisSum < 0) {
                thisSum = 0; // Reset running sum.
            }
        }
        return maxSum;
    }

    private static int rand(java.util.Random r, int min, int max) {
        return r.nextInt(max - min + 1) + min;
    }

    public static void main(String[] args) {

        // used with {"5"}, the output is nicely formatted

        // get the param argument
        int size = Integer.parseInt(args[0]);

        // populate a random array
        int[] randArray = getRandArray((long)size);

        // print every random number you got
        for (int i : randArray)
            System.out.printf("%3d", i);

        System.out.printf("%nMax Sum N^3:%3d", subSum_N1(getRandArray(65536L)));

        System.out.printf("%nMax Sum N^3:%3d", subSum_N3(randArray));

        System.out.printf("%nMax Sum N^2:%3d", subSum_N2(randArray));

        // Efficiency Testing

        int[] testArray = getRandArray(4096L);
        System.out.printf("%n%nTesting N^2 against N^3 for efficiency on a %d-element array...%nGO!%n%n", testArray.length);
        Stopwatch s = new Stopwatch();

        s.start(); System.out.printf("Max Sum N^1: %d", subSum_N1(testArray));
        s.stop();  System.out.printf("%nTime: %d ms%n", s.getElapsedTime());

        s.start(); System.out.printf("Max Sum N^2: %d", subSum_N2(testArray));
        s.stop();  System.out.printf("%nTime: %d ms%n", s.getElapsedTime());

        s.start(); System.out.printf("Max Sum N^3: %d", subSum_N3(testArray));
        s.stop();  System.out.printf("%nTime: %d ms%n", s.getElapsedTime());
    }

    public static int[] getRandArray(long size) {

        // populate a random array
        ArrayList<Integer> arr = new ArrayList<Integer>();
        java.util.Random randSeed = new java.util.Random();
        for (int i = 0; i < size; i++) {
            arr.add(rand(randSeed, -9, 10));
        }
        return arrayListToArray(arr);
    }

    public static int[] arrayListToArray(ArrayList<Integer> ints)
    {
        int[] r = new int[ints.size()];

        for (int i=0; i < r.length; i++)
            r[i] = ints.get(i);

        return r;
    }

}