Modify Algorithm 2, 3 & 4 so that they return in the value of the maximum subsequence and the starting and ending indices of the maximum subsequence. Your algorithm should take input size (N) from the user and generate a random sequence of N integers ranging from -9999 to 9999. If N is less than 50, your program must print the randomly generated numbers, and find the maximum subsequence. Your program should measure (print) the execution time of these algorithms (Algorithm 2, 3 & 4) in nanoseconds.

Here is the code provided:

MaxSumTest.java

import java.util.Random;

// This includes additional code not in the text that keeps

// track of the starting and ending points of best sequence

public final class MaxSumTest

{

/**

* Cubic maximum contiguous subsequence sum algorithm.

* seqStart and seqEnd represent the actual best sequence.

*/

public static int maxSubSum1( int [ ] a )

{

int maxSum = 0;

for( int i = 0; i

for( int j = i; j

{

int thisSum = 0;

for( int k = i; k =>

thisSum += a[ k ];

if( thisSum > maxSum )

{

maxSum = thisSum;

}

}

return maxSum;

}

/**

* Quadratic maximum contiguous subsequence sum algorithm.

* seqStart and seqEnd represent the actual best sequence.

*/

public static int maxSubSum2( int [ ] a )

{

int maxSum = 0;

for( int i = 0; i

{

int thisSum = 0;

for( int j = i; j

{

thisSum += a[ j ];

if( thisSum > maxSum )

{

maxSum = thisSum;

}

}

}

return maxSum;

}

/**

* Linear-time maximum contiguous subsequence sum algorithm.

* seqStart and seqEnd represent the actual best sequence.

*/

public static int maxSubSum4( int [ ] a )

{

int maxSum = 0;

int thisSum = 0;

for( int j = 0; j

{

thisSum += a[ j ];

if( thisSum > maxSum )

{

maxSum = thisSum;

}

else if( thisSum

{

thisSum = 0;

}

}

return maxSum;

}

/**

* Recursive maximum contiguous subsequence sum algorithm.

* Finds maximum sum in subarray spanning a[left..right].

* Does not attempt to maintain actual best sequence.

*/

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

{

int maxLeftBorderSum = 0, maxRightBorderSum = 0;

int leftBorderSum = 0, rightBorderSum = 0;

int center = ( left + right ) / 2;

if( left == right ) // Base case

return a[ left ] > 0 ? a[ left ] : 0;

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

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

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

{

leftBorderSum += a[ i ];

if( leftBorderSum > maxLeftBorderSum )

maxLeftBorderSum = leftBorderSum;

}

for( int i = center + 1; i =>

{

rightBorderSum += a[ i ];

if( rightBorderSum > maxRightBorderSum )

maxRightBorderSum = rightBorderSum;

}

return max3( maxLeftSum, maxRightSum,

maxLeftBorderSum + maxRightBorderSum );

}

/**

* Return maximum of three integers.

*/

private static int max3( int a, int b, int c )

{

return a > b ? a > c ? a : c : b > c ? b : c;

}

/**

* Driver for divide-and-conquer maximum contiguous

* subsequence sum algorithm.

*/

public static int maxSubSum3( int [ ] a )

{

return a.length > 0 ? maxSumRec( a, 0, a.length - 1 ) : 0;

}

/**

* Simple test program.

*/

public static void main( String [ ] args )

{

int a[ ] = { 4, -3, 5, -2, -1, 2, 6, -2 };

int maxSum;

maxSum = maxSubSum1( a );

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

maxSum = maxSubSum2( a );

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

maxSum = maxSubSum3( a );

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

maxSum = maxSubSum4( a );

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

}

}

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

ExecutionTimer.java

public class ExecutionTimer {

private long start;

private long end;

public ExecutionTimer() {

reset();

}

public void start() {

start = System.nanoTime();

}

public void end() {

end = System.nanoTime();

}

public long duration(){

return (end-start);

}

public void reset() {

start = 0;

end = 0;

}

public void print() {

System.out.print(duration()+\",\");

}

}