executionTimer.java

package maxsumtest;

public class ExecutionTimer {

private long start;

private long end;

public ExecutionTimer() {

reset();

}

public void start() {

start = System.currentTimeMillis();

}

public void end() {

end = System.currentTimeMillis();

}

public long duration(){

return (end-start);

}

public void reset() {

start = 0;

end = 0;

}

public void print() {

System.out.println("Execution Time:" + duration()+" milliseconds");

}

}

-----------------------------------------------------------

maxSumTest.java

package maxsumtest;

import java.util.Scanner;

public class maxSumTest {

public static void main(String[] args) {

Scanner reader = new Scanner(System.in); // Reading from System.in

System.out.print("Please enter the size of the problem (N): ");

int n = reader.nextInt();

reader.close();

int[] numbers = new int[n];

numbers = generateRandomNumbers(n);

ExecutionTimer executionTimer = new ExecutionTimer();

ExecutionTimer executionTimer2 = new ExecutionTimer();

ExecutionTimer executionTimer3 = new ExecutionTimer();

int startIndex = 10;

int endIndex = 14;

//Algorithms 2

executionTimer.start();

int algo2Result = maxSubSum2(numbers);

executionTimer.end();

System.out.println("Algorithm 2:");

System.out.println(String.format("MaxSum: %d, S index: %d, E index: %d",algo2Result, startIndex,endIndex));

executionTimer.print();

//Algorithms 3

executionTimer2.start();

int algo3Result = maxSumRec(numbers,10,14);

executionTimer2.end();

System.out.println("Algorithm 3:");

System.out.println(String.format("MaxSum: %d, S index: %d, E index: %d",algo3Result, startIndex,endIndex));

executionTimer2.print();

//Algorithms 4

executionTimer3.start();

int algo4Result = maxSubSum4(numbers);

executionTimer3.end();

System.out.println("Algorithm 4:");

System.out.println(String.format("MaxSum: %d, S index: %d, E index: %d",algo4Result, startIndex,endIndex));

executionTimer3.print();

}

/**

* Quadratic maximum contiguous subsequence sum algorithmm

*/

public static int maxSubSum2(int[] a) {

int maxSum = 0;

for (int i = 0; i < a.length; i++) {

int thisSum = 0;

for (int j = 0; j < a.length; j++) {

thisSum += a[j];

if (thisSum> maxSum) {

maxSum = thisSum;

}

}

}

return maxSum;

}

/**

* Recursive maximum contiguous subsequence sum algorithm.

* Finds maximum sum in sub-array spanning a[left..right].

* Does not attempt to maintain actual best sequence.

*/

private static int maxSumRec(int[] a, int left, int right ){

if (left == right) { //Base case

if (a[left] > 0) {

return a[left];

}

else {

return 0;

}

}

int center = (left + right)/2;

int maxLeftSum = maxSumRec(a, left, center);

int maxRightSum = maxSumRec(a, center+1, right);

int maxLeftBorderSum = 0, leftBorderSum =0;

for (int i = center; i >= left; i--) {

leftBorderSum += a[i];

if (leftBorderSum > maxLeftBorderSum) {

maxLeftBorderSum = leftBorderSum;

}

}

int maxRightBorderSum = 0, rightBorderSum = 0;

for (int i = center +1; i <= right; i++) {

rightBorderSum += a[i];

if (rightBorderSum > maxRightBorderSum) {

maxRightBorderSum = rightBorderSum;

}

}

int maxSum = Math.max(Math.max(maxLeftSum, maxRightSum), maxLeftBorderSum + maxRightBorderSum);

return maxSum;

}

/**

* Linear-time maximum contiguous subsequence sum algorithms

*/

public static int maxSubSum4(int[] a) {

int maxSum = 0, thisSum = 0;

for (int j = 0; j < a.length; j++) {

thisSum += a[j];

if (thisSum > maxSum) {

maxSum = thisSum;

}

else {

thisSum = 0;

}

}

return maxSum;

}

private static int[] generateRandomNumbers(int totalNumber) {

int minValue = -9999;

int maxValue = 9999;

int numbers[] = new int[totalNumber];

for (int i = 0; i < totalNumber; i++) {

int temp = (int) (Math.random()*(maxValue - minValue)) + minValue;

numbers[i] = temp;

}

if (numbers.length<50) { //print only if less than 50 numbers

for (int i = 0; i < numbers.length; i++) {

System.out.print(String.format("%d ", numbers[i]));

}

}

System.out.println("");

return numbers;

}

}

-------------------------------------------------

Javac maxsumtest.java

maxSumTest.java:29: error: cannot find symbol ExecutionTimer executionTimer = new ExecutionTimer(); ^ symbol: class ExecutionTimer location: class maxSumTest maxSumTest.java:29: error: cannot find symbol ExecutionTimer executionTimer = new ExecutionTimer(); ^ symbol: class ExecutionTimer location: class maxSumTest maxSumTest.java:30: error: cannot find symbol ExecutionTimer executionTimer2 = new ExecutionTimer(); ^ symbol: class ExecutionTimer location: class maxSumTest maxSumTest.java:30: error: cannot find symbol ExecutionTimer executionTimer2 = new ExecutionTimer(); ^ symbol: class ExecutionTimer location: class maxSumTest maxSumTest.java:31: error: cannot find symbol ExecutionTimer executionTimer3 = new ExecutionTimer(); ^ symbol: class ExecutionTimer location: class maxSumTest maxSumTest.java:31: error: cannot find symbol ExecutionTimer executionTimer3 = new ExecutionTimer(); ^ symbol: class ExecutionTimer location: class maxSumTest 6 errors