Please use the listed algorithms for solving the problem of finding a maximum subsequence sum of a given a sequence of integers for Parts A and B. The code should be in JAVA

Algorithm #1: Exhaustive

Algorithm #2: Algorithm that removes the inner loop

Algorithm #3: Recursive Divide and Conquer

Algorithm #4: Dynamic Programming Method

PART A

Rewrite the algorithms above to find the boundary indices (two indices) of a maximum subsequence and also the value of maximum subsequence sum.

Part B

Test the programs for different data sets of size 1000, 10000, 100000, one million, and 10 millions, and find the CPU time for each data set and algorithm. Use a random number generator to generate data sets.

int maxSubSum 1( int[] a) { int maxSum = 0; for(int i = 0; i maxSum ) maxSum - this Sum; = } return maxSum; } int maxSubSum2(int[] a) { int maxSum = 0; for(int i = 0; i maxSum ) maxSum = this Sum; } return maxSum; } 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 = maxSumRecla, center + 1, right); Continued on Next Page Integer.MIN_VALUE = -2147483648 Smallest number represented language int maxLeftBorderSum = INT_MIN, leftBorderSum = 0; for(int i = center; i >= left; --i) { leftBorderSum += a[i]; if(leftBorderSum > maxLeftBorderSum) maxLeftBorderSum = leftBorderSum; } int maxRightBorderSum = INT_MIN, rightBorderSum = 0; for(int j = center+1; j maxRightBorderSum) maxRightBorderSum = rightBorderSum; } return max3(maxLeftSum, maxRight Sum, maxLeftBorderSum + maxRightBorderSum); } int maxSub Sum4( int[] a ) {. int maxSum = 0, this Sum = 0; for(int j = 0; j maxSum) maxSum = this Sum; else if( this Sum