/*

file: MaxRunSum

notes:  used to demo the running time of various algorithms
        to solve the maximum run sum problem


usage:
  java MaxRunSum [<n> [<seed>] [--quiet]]
  java MaxRunSum [--ints [quiet]]
      n  the number of ints to randomly generate
   seed  for rng (if unspecified a random seed is used)
--quiet  the string "quiet" means don't show the sequence
 --ints  use user supplied sequence, format is one int per line
*/

import java.util.Random;
import java.util.Vector;
import java.io.*;


public class MaxRunSum  {


public static void main (String[] arguments) throws Exception {

   // how many numbers to sort?
   int size = 0;
   boolean userSupplied = false;

   if (arguments.length == 0)
      // usage message if no inputs provided
      throw (new Exception ("usage:\n java MaxRunSum <n> [<seed>] [--quiet]"));
   else if (arguments[0].equals("--ints"))
      // read integers from std input
      userSupplied = true;
   else
      // if specified on command line
      size = Integer.parseInt (arguments[0]);

   // determine numbers to be sorted
   // otherwise use random numbers, user may specify
   // the rng seed if they wish
   // if 2nd arg is "--quiet" then no seed has been specified

   Random rng = new Random();

   if (arguments.length > 1)
      if (! arguments[1].equals("--quiet")) {
         long seed = Long.parseLong (arguments[1]);
         rng.setSeed(seed);
      }

   // if a 2nd or 3rd argument is "quiet" then sorted output
   // is suppressed
   boolean silent =
      ((arguments.length > 2) && (arguments[2].equals("--quiet"))) ||
      ((arguments.length > 1) && (arguments[1].equals("--quiet")));


   // load sequence to be analysed into an array
   int[] data = new int[size];

// read in data if user supplied
   if (userSupplied) {
      Vector lines = new Vector();
      BufferedReader in
         = new BufferedReader(new InputStreamReader(System.in));
      try {
         String line = in.readLine();
         while (! line.equals("")) {
            lines.add(line);
            line = in.readLine();
         }
      } catch (Exception e) {}

      data = new int[lines.size()];
      for (int i=0; i<lines.size(); i++)
         data[i] = Integer.parseInt((String) lines.get(i));

   } else {
      int maxValue = 2*size;  //
      // load some (random) data into the array
      // each number in the range -2*size..2*size-1
      // *2 so we get some gaps
      for (int i=0; i < size; i++)
         data [i] = (rng.nextInt()) % maxValue;
   }

   // note what time we start
   long start = System.currentTimeMillis();

   // -------------------------------------------------------------
   // find max subsequence sum - using one of the algorithms below
   // -------------------------------------------------------------
   long solution = subseqE(data);
   // -------------------------------------------------------------

   // work out how much time has passed
   long elapsed = System.currentTimeMillis() - start;

   System.out.println("Max sum is "+solution);

   // print out the sequence (to convince us it worked)
   if (! silent)
      for (int pos=0; pos < data.length; pos++) {
         if (pos > 0)
            System.out.print(", ");
         System.out.print (""+data[pos]);
      }
   System.out.println();
   System.out.println();

   // print statistics
   System.out.println ("-- Statistics --");
   System.out.println ("   Items: "+size);
   System.out.println ("    Time: "+elapsed+"ms");

}


//   algorithm A from lecture 1
public static long subseqA(int[] data) {

   System.out.println("Algorithm A");
   // consider all sequences lower..upper by considering
   // all pairs of endpoints
   long maxSoFar = 0;
   int last = data.length - 1;
   long sum;

   for (int lower=0; lower<=last; lower++)
      for (int upper=lower; upper<=last; upper++) {
         sum = 0;
         for (int i=lower; i<=upper; i++)
            sum = sum + data[i];

         maxSoFar = Math.max (maxSoFar, sum);
      }

   return (maxSoFar);
}


// algorithm B from lecture 2

//consider all sequences lower..upper by considering
// all pairs of endpoints , but smarter calc of the sum
// X[lower]..X[upper] using sum of
// X[lower]..X[upper-1]
public static long subseqB(int[] data) {
   System.out.println("Algorithm B");

   long maxSoFar = 0;
   int last = data.length - 1;
   long sum;

   for (int lower=0; lower<=last; lower++) {
      sum = 0;
      for (int upper=lower; upper<=last; upper++) {
         sum = sum + data[upper];
         maxSoFar = Math.max (maxSoFar, sum);
      }
   }
   return (maxSoFar);
}


//  algorithm C from lecture 2

//consider all sequences lower..upper by considering
// all pairs of endpoints , but smarter calc of the sum
// X[lower]..X[upper] precomputing partial sums
public static long subseqC(int[] data) {
   System.out.println("Algorithm C");

   long maxSoFar = 0;
   int last = data.length - 1;
   long sum;
   long[] totals = new long[data.length+1];

   totals[0]=0;

   for (int i=0; i<=last; i++)
      totals[i+1]=totals[i]+data[i];


   for (int lower=0; lower<=last; lower++)
      for (int upper=lower; upper<=last; upper++) {
         sum = totals[upper+1] - totals[lower];
         maxSoFar = Math.max (maxSoFar, sum);
      }
   return (maxSoFar);
}


// algorithm D (divide and conquer) - week 3 lecture

// (recursively) find the max subseqsum in the first half
// of the sequence, the max subseqsum in the second half of
// the sequence, and the max subseqsum which crosses
// the boundary between the first and second halves

public static long subseqD(int[] data) {
   System.out.println("Algorithm D");

   int last = data.length - 1;
   return (maxSumD (0,last,data));
}

public static long maxSumD (int lower, int upper, int[] data) {
   if (lower>upper) {
//      System.out.println("A "+lower+" "+upper);
      return (0);
   }

   if (lower==upper) {
//      System.out.println("A "+lower+" "+upper);
      return (Math.max(0,data[lower]));
   }

   int mid = (lower+upper) / 2;

//   System.out.println("C "+lower+" "+mid+" "+upper);

   // find maxsum which includes mid
   long sum = 0;
   long midLeftMax  = 0;
   long midRightMax = 0;
   long midMax   = 0;
   long leftMax  = 0;
   long rightMax = 0;

   // max sum to left
   for (int i=mid-1; i>=lower; i--) {
      sum=sum+data[i];
      midLeftMax = Math.max (sum, midLeftMax);
   }

   // max sum to right
   sum=0;
   for (int i=mid+1; i<=upper; i++) {
      sum=sum+data[i];
      midRightMax = Math.max (sum, midRightMax);
   }

    // max sum including mid item
    midMax = data[mid] + midLeftMax + midRightMax;
//    System.out.println ("left");
    leftMax  = maxSumD(lower, mid-1, data);
//    System.out.println ("right");
    rightMax = maxSumD(mid+1, upper, data);

    return (Math.max (leftMax, (Math.max (rightMax, midMax))));
}


// using algorithm from lecture week 7
// see "programming pearls"  Jon Bently

// notice - we just find the size of the max sum of a run,
// we don't find the run itself - typical feature of dynamic
// programming problems.

public static long subseqE(int[] data) {
   System.out.println("Algorithm E");

   long maxSoFar = 0;
   long maxEndingHere = 0;

   for (int i=0; i<data.length; i++) {
      maxEndingHere = Math.max(maxEndingHere+data[i],0);
      maxSoFar      = Math.max(maxSoFar, maxEndingHere);
   }
   return (maxSoFar);
}
} // end of class


and


timings for max subseq problem


n    chksum  orithmA  algorithmB  algorithmC  algorithmD   E
    mod 100
10       62       20           0           0
100      90       41          10          10          20
1000     10     1452          40          50          10  10
2000     78    11076          90         120          30  20
4000     94    88497         250         270          40
10000    11                 1201        1412          50
100000   28               158138      177545         100  20
1000000  83                                          931  90
10000000                                           11000 791