The program segment below shows four different implementations for the max sub-sequence sum task.

Compare the performance of the four different implementations as follows:

1. Compare the execution time for different values of N ={1000,2000,3000,...,20000}

2. Use random number generator to produce an array of integers in the range (-1000,1000)

3. Computer the elapsed time of each implementation for each value of N.

4. Draw the curves showing the elapsed time vs N.

5. What is the time complexity of each implementation?

=========================================

int maxSubSum1(int* a, int n) { int maxSum = 0; for (int i = 0; i < n; ++i) for (int j = i; j < n; ++j) { int thisSum = 0; for (int k = i; k <= j; ++k) thisSum += a[k]; if (thisSum > maxSum) maxSum = thisSum; } return maxSum; }

int maxSubSum2(int* a, int n) { int maxSum = 0; for (int i = 0; i < n; ++i) { int thisSum = 0; for (int j = i; j < n; ++j) { thisSum += a[j]; if (thisSum > maxSum) maxSum = thisSum; } } return maxSum; }

int maxSumRec(int* a, int left, int right) { if (left == right) return a[left] > 0 ? a[left] : 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 j = center + 1; j <= right; ++j) { rightBorderSum += a[j]; if (rightBorderSum > maxRightBorderSum) maxRightBorderSum = rightBorderSum; } int temp = maxLeftBorderSum + maxRightBorderSum; if (maxLeftSum >= maxRightSum & maxLeftSum >= temp) return maxLeftSum; if (maxRightSum > temp) return maxRightSum; return temp; }

int maxSubSum3(int* a, int n) { return maxSumRec(a, 0, n - 1); }

int maxSubSum4(int* a, int n) {

int maxSum = 0, thisSum = 0; for (int j = 0; j < n; ++j) { thisSum += a[j]; if (thisSum > maxSum) maxSum = thisSum; else if (thisSum < 0) thisSum = 0; } return maxSum; }