URGENT: Hello, please help completing the following Problem IN C++: (I WILL RATE. THANK YOU.)

Exercise 2.19: 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.

Write a program that solves Exercise 2.19 in C++. You need to modify the programs for each of the 4 algorithms for the maximum-subsequence-sum problem so that the program not only returns the maximum sums of subsequences of the given integer array but also returns/outputs the actual subsequence where the sum of integers is maximum.

I HAVE THE CODE AND WILL BE ATTACHED BELOW THE ALGORITHMS. I NEED HELP IN THE FOLLOWING PART: Run each algorithm on three randomly generated integer arrays of sizes N=1,000, 10,000, and 100,000, measure the running times, and determine if they are consistent with the theoretical analysis results of those algorithms given in class, i.e., if the running time of algorithm 1 for the MSS problem is proportional to N3 and that for Algorithm 2 is proportional to N2 , etc. Include a table in your report that summarizes the actual running times (in appropriate time units) and narrative about your observations regarding whether the implemented algorithms indeed demonstrate behaviors entailed by theoretical analysis.

Algorithm 1:

ALGORITHM 2:

ALGORITHM 3:

ALGORITHM 4:

CODE:

#include "stdafx.h"

#include

#include

using namespace std;

// Cubic maximum contiguous subsequence sum algorithm.

int maxSubSum1(const vector & 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.

int maxSubSum2(const vector & 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;

}

// Return maximum of three integers.

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

{

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

}

/**

* Recursive maximum contiguous subsequence sum algorithm.

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

* Does not attempt to maintain actual best sequence.

*/

int maxSumRec(const vector & 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 j = center + 1; j

{

rightBorderSum += a[j];

if (rightBorderSum > maxRightBorderSum)

maxRightBorderSum = rightBorderSum;

}

return max3(maxLeftSum, maxRightSum,

maxLeftBorderSum + maxRightBorderSum);

}

// Driver for divide-and-conquer maximum contiguous

// subsequence sum algorithm.

int maxSubSum3(const vector & a)

{

return maxSumRec(a, 0, a.size() - 1);

}

// Linear-time maximum contiguous subsequence sum algorithm.

int maxSubSum4(const vector & a)

{

int maxSum = 0, thisSum = 0;

for (int j = 0; j

{

thisSum += a[j];

if (thisSum > maxSum)

maxSum = thisSum;

else if (thisSum

thisSum = 0;

}

return maxSum;

}

// main

int main()

{

// Declaration of a vector.

vector a(8);

a[0] = 6; a[1] = -7; a[2] = 2; a[3] = -3;

a[4] = -5; a[5] = 4; a[6] = 6; a[7] = -4;

// Declaration of a variable of integer datatype.

int maxisum;

maxisum = maxSubSum1(a);

cout

maxisum = maxSubSum2(a);

cout

maxisum = maxSubSum3(a);

cout

maxisum = maxSubSum4(a);

cout

system("pause");

return 0;

}

2 Quadratic maximum contiguous subsequence sum algorithm. 4 int maxSubSum2( const vector & a ) int maxSum - 0; for( inti-0; i maxSum) maxSum th sSum; return maxSum; 2 Recursive maximum contiguous subsequence sum algorithm 3Finds maximum sum in subarray spanning a[left..right]. 4Does not attempt to maintain actual best sequence 6 int maxSumRec const vector & a, int left, int right) f leftright// Base case 9 if a left ] >0) 10 return a left ]; else 12 13 return 0 nt centereft right) /2; int maxLeftSummaxSumRec( a, left, center); 1nt maxR1ghtSum maxSumRec( a, center1, right); 15 16 17 18 19 20 21 int maxleftBordersum- 0, leftBorderSum for( int 1 center 1eft;) 0; 1eftBordersum += a[ 1 ]; if( leftBorderSum >maxLeftBorderSum 23 24 25 26 27 28 29 30 31 32 maxLeftBorderSumleftBorderSum 1nt maxR1ghtBorderSum 0, rightBorderSum 0; for( int j- center1; j right; +j) rightBorderSumal j ]; if( rightBorderSum>maxR1ghtBorderSum) maxRightBorderSum- rightBorderSum; 34 35 return max3( maxLeftSum, maxR1ghtSum, maxLeftBorderSummaxR1ghtBorderSum); 37 38 / 39 Driver for divide-and-conquer maximum contiguous 40subsequence sum algorithm 41 42 nt maxSubSum3( const vector int>& a 43 44 return maxSumRec( a, o, a.size) -1) 45 Figure 2.7 Algorithm3 2 Linear-time max1mum contiguous subsequence sum algorithm. 4 int maxSubSum4 ( const vector & a ) int maxsum 0, th ssum = 0; for( int j = 0; j a.size( ); +tJ ) 10 thissum +-a[ j ]; 12 13 14 15 16 17 18 19 if thisSum > maxSum) maxSum = thi sSum; else if( thisSum & a ) int maxSum - 0; for( inti-0; i maxSum) maxSum th sSum; return maxSum; 2 Recursive maximum contiguous subsequence sum algorithm 3Finds maximum sum in subarray spanning a[left..right]. 4Does not attempt to maintain actual best sequence 6 int maxSumRec const vector & a, int left, int right) f leftright// Base case 9 if a left ] >0) 10 return a left ]; else 12 13 return 0 nt centereft right) /2; int maxLeftSummaxSumRec( a, left, center); 1nt maxR1ghtSum maxSumRec( a, center1, right); 15 16 17 18 19 20 21 int maxleftBordersum- 0, leftBorderSum for( int 1 center 1eft;) 0; 1eftBordersum += a[ 1 ]; if( leftBorderSum >maxLeftBorderSum 23 24 25 26 27 28 29 30 31 32 maxLeftBorderSumleftBorderSum 1nt maxR1ghtBorderSum 0, rightBorderSum 0; for( int j- center1; j right; +j) rightBorderSumal j ]; if( rightBorderSum>maxR1ghtBorderSum) maxRightBorderSum- rightBorderSum; 34 35 return max3( maxLeftSum, maxR1ghtSum, maxLeftBorderSummaxR1ghtBorderSum); 37 38 / 39 Driver for divide-and-conquer maximum contiguous 40subsequence sum algorithm 41 42 nt maxSubSum3( const vector int>& a 43 44 return maxSumRec( a, o, a.size) -1) 45 Figure 2.7 Algorithm3 2 Linear-time max1mum contiguous subsequence sum algorithm. 4 int maxSubSum4 ( const vector & a ) int maxsum 0, th ssum = 0; for( int j = 0; j a.size( ); +tJ ) 10 thissum +-a[ j ]; 12 13 14 15 16 17 18 19 if thisSum > maxSum) maxSum = thi sSum; else if( thisSum