package analysis;

import java.util.*;

public final class MaxSumTest {
    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;
    }

    /**
     * Simple test program.
     */
    public static void main(String[] args) {
        int a[] = {};
        int maxSum = 0;

        for (int N = 100; N < 2000000; N *= 2) {
            a = new int[N];
            Random r = new Random();
            for (int i = 0; i < N; i++)
                a[i] = r.nextInt(N + 1) - N / 2;

            long start, end;
            long elapsed1 = 0, elapsed2 = 0, elapsed3 = 0;

            /*
             */
            start = System.nanoTime();
            maxSum = maxSubSum1(a);
            end = System.nanoTime();

            elapsed1 = end - start;
            System.out.println("Max sum is " + maxSum + "; it goes" + " from "
                    + seqStart + " to " + seqEnd);

            start = System.nanoTime();
            maxSum = maxSubSum2(a);
            end = System.nanoTime();

            elapsed2 = end - start;
            System.out.println("Max sum is " + maxSum + "; it goes" + " from "
                    + seqStart + " to " + seqEnd);

            start = System.nanoTime();
            maxSum = maxSubSum3(a);
            end = System.nanoTime();

            elapsed3 = end - start;
            System.out.println("Max sum is " + maxSum + "; it goes" + " from "
                    + seqStart + " to " + seqEnd);

            System.out.println("size: " + N + "\t" + "times: " + "\t"
                    + (elapsed1) + "ns\t" + (elapsed2) + "ns\t" + (elapsed3) +"ns");
            System.out.println("\t    (in secs): " + "\t"
                    + nanoToSeconds(elapsed1) + "\t" + nanoToSeconds(elapsed2)
                    + "\t" + nanoToSeconds(elapsed3));

            // System.out.println("time1/N^3: " +
            // (double)elapsed1/((double)N*N*N)); System.out.println("time2/N^2:
            // " +
            // (double)elapsed2/((double)N*N)); System.out.println("time3/N: " +
            // (double)elapsed3/((double)N));

        }
    }

    public static String nanoToSeconds(long nanoseconds) {
        return round(nanoseconds * Math.pow(10.0, -9.0) , 2) + "s";
    }

    public static double round(double value, int decimalPlace) {
        double power_of_ten = 1;
        while (decimalPlace-- > 0)
            power_of_ten *= 10.0;
        return Math.round(value * power_of_ten) / power_of_ten;
    }

}