Modify Algorithm 2 (pg 41) and Algorithm 4 (pg 44) to return an object that contains 3 values, the sum, the start index, the end index for the maximum sub-sequence sum (you can use an array, or a custom object) The maximum contiguous subsequence sum algorithms in the text do not give any indication of the actual sequence. Modify them so that they return in a single object the value of the maximum subsequence and the indices of the actual sequence. Algorithm 2 /** * Quadratic maximum contiguous subsequence sum algorithm. */ public static int maxSubSum2( int [ ] a ) { int maxSum = 0; for( int i = 0; i < a.length; i++ ) { int thisSum = 0; for( int j = i; j < a.length; j++ ) { thisSum += a[ j ]; if( thisSum > maxSum ) maxSum = thisSum; } } return maxSum; }

Algorithm 4 /** * Linear-time maximum contiguous subsequence sum algorithm. */ 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 if( thisSum < 0 ) thisSum = 0; } return maxSum; }