<![CDATA[
// Stuart Reges handout #12
// 4/13/05
//
// This program explores three different solutions to the problem of finding
// the maximum sum possible given a sequence of integers. The program
// constructs an array of random integers between -500 and +500 and runs
// each of the three algorithms, keeping track of how much time they take
// to run.
import java.util.*;
public class MaxSum {
public static final boolean DEBUGGING = false; // if true, we see list
// contents
public static void main(String[] args) {
// find out how big of a list to process
Scanner console = new Scanner(System.in);
System.out.print("How many numbers do you want to use? ");
int n = console.nextInt();
// construct the list
int[] numbers = new int[n];
for (int i = 0; i < n; i++)
numbers[i] = (int)(1001 * Math.random()) - 500;
// need some timing variables and print the list if debugging
long start;
double elapsed;
if (DEBUGGING)
printRange(numbers, 0, n - 1);
// test of algorithm 1
start = System.currentTimeMillis();
findMax1(numbers);
elapsed = (System.currentTimeMillis() - start)/1000.0;
System.out.println("findMax1 took " + elapsed + " seconds");
System.out.println();
// test of algorithm 2
start = System.currentTimeMillis();
findMax2(numbers);
elapsed = (System.currentTimeMillis() - start)/1000.0;
System.out.println("findMax2 took " + elapsed + " seconds");
System.out.println();
// test of algorithm 3
start = System.currentTimeMillis();
findMax3(numbers);
elapsed = (System.currentTimeMillis() - start)/1000.0;
System.out.println("findMax3 took " + elapsed + " seconds");
System.out.println();
}
// This method uses the brute force method of finding every possible
// starting and stopping index and adding up the values in that range.
// It has O(n^3) complexity. Assumes list.size > 0.
public static void findMax1(int[] list) {
// initalize max sequence to just the first element of the list
int max = list[0];
int maxStart = 0;
int maxStop = 0;
long lineCount = 0;
for (int start = 0; start < list.length; start++)
for (int stop = start; stop < list.length; stop++) {
int sum = 0;
for (int k = start; k <= stop; k++) {
sum += list[k];
lineCount++;
}
if (sum > max) {
max = sum;
maxStart = start;
maxStop = stop;
}
}
System.out.println("Max = " + max);
System.out.println("Max start = " + maxStart);
System.out.println("Max stop = " + maxStop);
System.out.println("Line count = " + lineCount);
if (DEBUGGING)
printRange(list, maxStart, maxStop);
}
// This method improves on the brute force method by keeping partial sums
// instead of recomputing from scratch each time. It has O(n^2)
// complexity. Assumes list.size > 0.
public static void findMax2(int[] list) {
// initalize max sequence to just the first element of the list
int max = list[0];
int maxStart = 0;
int maxStop = 0;
long lineCount = 0;
for (int start = 0; start < list.length; start++) {
int sum = 0;
for (int stop = start; stop < list.length; stop++) {
lineCount++;
sum += list[stop];
if (sum > max) {
max = sum;
maxStart = start;
maxStop = stop;
}
}
}
System.out.println("Max = " + max);
System.out.println("Max start = " + maxStart);
System.out.println("Max stop = " + maxStop);
System.out.println("Line count = " + lineCount);
}
// This method keeps a running sum, resetting the starting point and
// resetting the sum to 0 if the sum ever goes negative. It has O(n)
// complexity. Assumes list.size > 0.
public static void findMax3(int[] list) {
// initalize max sequence to just the first element of the list
int max = list[0];
int maxStart = 0;
int maxStop = 0;
long lineCount = 0;
int start = 0;
int sum = 0;
for (int i = 0; i < list.length; i++) {
lineCount++;
if (sum < 0) {
start = i;
sum = 0;
}
sum += list[i];
if (sum > max) {
max = sum;
maxStart = start;
maxStop = i;
}
}
System.out.println("Max = " + max);
System.out.println("Max start = " + maxStart);
System.out.println("Max stop = " + maxStop);
System.out.println("Line count = " + lineCount);
}
// pre : 0 <= start <= stop < numbers.length
// Prints the specified range of numbers 15 per line
public static void printRange(int[] numbers, int start, int stop) {
int count = 0;
for (int i = start; i <= stop; i++) {
System.out.print(numbers[i] + " ");
count++;
if (count % 15 == 0)
System.out.println();
}
System.out.println();
System.out.println();
}
}
]]>