In this assignment, you will devise an algorithm with time complexity O(n^2) that finds the maximum subsequence sum. For extra credit (5 points), you may devise an algorithm that finds the maximum subsequence sum with time complexity O(n).

Please download the starter files code below for this assignment. Do not alter the function definitions or driver code in any way. Programs that crash are subject to a 50% penalty. PLEASE NOTE: You may not use any Standard Template Library (STL) classes for this assignment.

The Maximum Subsequence Sum Problem is described as follows: Given (possibly negative) integers find the maximum sum over all subsequences

The following algorithm solves the maximum subsequence problem for time complexity O(n^2).

Please test and compile your code for errors before submitting code that contains bugs or that is not working. Thanks!

ProgramMax.cpp:

#include

using namespace std;

//** Brute Force Solution : O(n3)

int maxSequenceSum_N3(int A[], int n);

//** Brute Force Solution : O(n2)

int maxSequenceSum_N2(int A[], int n);

//** Optimal Solution : O(n)

int maxSequenceSum_N1(int A[], int n);

int main()

{

srand(77); // Initialize random seed

int A[100];

for (int i = 0; i

{

int sign = pow(-1, (rand() % 2 + 1));

A[i] = (rand() % 100 + 1) * sign;

}

cout

cout

cout

system("pause");

return 0;

}

int maxSequenceSum_N3(int A[], int n)

{

int currentSum = 0, maxSum = std::numeric_limits::min(); // minimum value;

int i, j, k;

for (i = 0; i

{

for (j = i; j

{

currentSum = 0;

for (k = i; k

currentSum += A[k];

if (currentSum > maxSum)

maxSum = currentSum;

}

}

return (maxSum == std::numeric_limits::min()) ? 0 : maxSum;

}

int maxSequenceSum_N2(int A[], int n)

{

int currentSum = 0, maxSum = std::numeric_limits::min(); // minimum value;

//*** Write this algorithm ***

return (maxSum == std::numeric_limits::min()) ? 0 : maxSum;

}

int maxSequenceSum_N1(int A[], int n)

{

int currentSum = 0, maxSum = std::numeric_limits::min(); // minimum value;

//*** Write this algorithm ***

return (maxSum == std::numeric_limits::min()) ? 0 : maxSum;

}

a1, a2, aN, a1, a2, aN