/* T02n06 - These are examples of solutions of the maximum 
 * subsequence sum problem, described in any number of CS 2 texts written
 * by Mark Weiss, including "Data Structures and Algorithm Analysis in
 * Java."  Weiss probably got it from Jon Bentley's ``Programming Pearls''
 * book.  It's a 1D simplification of a 2D pattern recognition problem.
 *
 * The problem is easily described:  You have a sequence of integer
 * values.  Which contiguous subsequence of those values sums to the
 * largest value?  For example, 1 -2 3 -2 4 has a maximum subsequence sum
 * of 5: 3 + (-2) + 4.  It's an interesting problem because the obvious
 * solution is very inefficient, but with some thought, a very
 * efficient algorithm can be produced.
 *
 * I've modified Weiss' algorithms to suit my needs; in particular:
 *
 * (1) Rather than just pass in an array of int and assume that the array
 * is full, I also pass in the number of elements to be searched for the
 * maximum subsequence.  This is common practice in a lot of languages,
 * and I want you exposed to reality once in a while.
 *
 * (2) The "seqStart" and "seqEnd" variables were
 * removed.  At the end of the algorithms, they held the sequence endpoints.
 * Because I'm using these as examples of analysis, I didn't need them.
 *
 * Also note the use of System.currentTime.Millis() to measure the execution
 * times of the four algorithms.  Ideally, we want to measure the CPU time
 * that was spent on the calculation, not the "wall-clock" time.  
 * Unfortunately, Java has no stardard way to access that information from
 * the OS, and so rather than using a system-specific solution, we'll
 * settle for the execution time measurement.
 */

import java.io.*;
import java.util.*;           // for class Random

public class T02n06
{

    public static void createSequence(int [] list, int numElements)
    {
        Random random = new Random();

        for (int i=0; i<numElements; i++)
             list[i] = random.nextInt(11) - 5;
    }


// O(n^3)

    public static int maxSubsequenceSumV1(int [] list, int n)
    {
        int thisSum,
            maxSum = 0;

        for (int i=0; i<n; i++) {
            for (int j=i; j<n; j++) {
                thisSum = 0;
                for (int k=i; k<=j; k++) {
                    thisSum += list[k];
                }
                if (thisSum > maxSum) {
                    maxSum = thisSum;
                }
            }
        }

        return maxSum;
    }


// O(n^2)

    public static int maxSubsequenceSumV2(int [] list, int n)
    {
        int thisSum,
            maxSum = 0;

        for (int i=0; i<n; i++) {
            thisSum = 0;
            for (int j=i; j<n; j++) {
                thisSum += list[j];
                if (thisSum > maxSum) {
                    maxSum = thisSum;
                }
            }
        }

        return maxSum;
    }


// O(n log_2 n)

    public static int maxSubsequenceSumV3(int [] list, int n)
    {
        return recursiveMaxSubSum(list,0,n-1);
    }

    private static int recursiveMaxSubSum(int [] list, int left, int right)
    {
        int    maxLeftSum, maxRightSum,
               maxLeftBorderSum, maxRightBorderSum,
               leftBorderSum, rightBorderSum,
               center;

	if (left == right) { 	/* base case */
		if (list[left] > 0) {
                    return list[left]; 
                } else {
                    return 0;
                }
	}

        center = (left + right) / 2;
        maxLeftSum = recursiveMaxSubSum(list,left,center);
        maxRightSum = recursiveMaxSubSum(list,center+1,right);

        maxLeftBorderSum = leftBorderSum = 0;

        for (int i=center; i>=left; i--) {
            leftBorderSum += list[i];
            if (leftBorderSum > maxLeftBorderSum) {
                maxLeftBorderSum = leftBorderSum;
            }
        }

        maxRightBorderSum = rightBorderSum = 0;

        for (int i=center+1; i<=right; i++) {
            rightBorderSum += list[i];
            if (rightBorderSum > maxRightBorderSum) {
                maxRightBorderSum = rightBorderSum;
            }
        }

        return (Math.max(Math.max(maxLeftSum,maxRightSum),
                maxLeftBorderSum + maxRightBorderSum));

    }


// O(n)

    public static int maxSubsequenceSumV4(int [] list, int n)
    {
        int thisSum, maxSum;

	thisSum = maxSum = 0;

        for (int j=0; j<n; j++) {
            thisSum += list[j];
            if (thisSum > maxSum) {
                maxSum = thisSum;
            } else if (thisSum < 0) {
                thisSum = 0;
            }
        }

        return maxSum;
    }


    public static long startTiming ()
    {
        System.gc();
        return (System.currentTimeMillis());
    }

    public static double stopTiming (long startingTime)
    {
        long elapsedTime = System.currentTimeMillis() - startingTime;
        return (elapsedTime / 1000.0);    // return seconds
    }


    public static void main (String [] args)
    {
        int [] list;
        int listSize = 0;
        int sum;
        long startTime;
        double seconds;

        if (args.length == 0) {
            System.out.println("Usage: java T02n06 <list size>");
            System.exit(1);
        } else {
            listSize = Integer.parseInt(args[0]);
        }

        list = new int [listSize];

	createSequence(list,listSize);

        System.out.println("\nList size for this run:" 
                          + listSize + " items.\n");

        startTime = startTiming();
	sum = maxSubsequenceSumV1(list,listSize);
        seconds = stopTiming(startTime);
        System.out.println("Version 1 found the maximum sum to be " + sum
                          + " in " + seconds + " seconds.");

        startTime = startTiming();
	sum = maxSubsequenceSumV2(list,listSize);
        seconds = stopTiming(startTime);
        System.out.println("Version 2 found the maximum sum to be " + sum
                          + " in " + seconds + " seconds.");

        startTime = startTiming();
	sum = maxSubsequenceSumV3(list,listSize);
        seconds = stopTiming(startTime);
        System.out.println("Version 3 found the maximum sum to be " + sum
                          + " in " + seconds + " seconds.");

        startTime = startTiming();
	sum = maxSubsequenceSumV4(list,listSize);
        seconds = stopTiming(startTime);
        System.out.println("Version 4 found the maximum sum to be " + sum
                          + " in " + seconds + " seconds.");
    }
}