COP 3503C UCF Study Sheet #1

//used code from the following source: http://www.cs.ucf.edu/~dmarino/ucf/cop3503/lectures/AlgAnalysis03.doc
public class practice {
    public static void main(String[] args){
        int[] a = {9, -3, 7, -12, 3, -2, 5, -8, 8, 13, -20, 6, -4, 3, -5, 3, -2, 18, 9, -4, 5};
        MCSS(a);//this tests the O(n^2)
        MCSS2(a);//this tests the O(n)
    }
    //this tests the O(n^2)
    public static int MCSS(int [] a) {
         int max = 0, sum = 0, start = 0, end = 0;
         int count=0;
         // Try all possible values of start and end indexes for the sum.
         for (int i = 0; i < a.length; i++) {
              sum = 0;
              for (int j = i; j < a.length; j++) {
                   sum += a[j]; // No need to re-add all values.
                   if (sum > max) {
                       count++;
                       System.out.printf("Changed max at i= %d and j= %d\n"
                            + "\tNew max: %d\n"
                            + "\tChanges so far: %d\n", i, j, sum, count);
                       max = sum;
                       start = i; // Although method doesn't return these
                       end = j;  // they can be computed.
                   }
              }
         }
         System.out.printf("max: %d\n", max);
         return max;
    }
    //this tests the O(n)
    public static int MCSS2(int [] a) {

         int max = 0, sum = 0, start = 0, end = 0, i=0;
         int count = 0;

         // Cycle through all possible end indexes.
         for (int j = 0; j < a.length; j++) {

              sum += a[j]; // No need to re-add all values.
              if (sum > max) {
                  count++;
                  System.out.printf("Changed max at i=%d and j=%d\n"
                            + "\tNew max: %d\n"
                            + "\tChanges so far: %d\n", i, j, sum, count);
                  max = sum;
                  start = i; // Although method doesn't return these
                  end = j;  // they can be computed.
              }
              else if (sum < 0) {
                   i = j+1; // Only possible MCSSs start with an index >j.
                   sum = 0; // Reset running sum.
              }
         }
         System.out.printf("max: %d\n", max);
         return max;
    }


}