Maximum Subsequence Sum Problem. C++

Today I am loading some code to solve a simple problem called "The Maximum Subsequence Sum Problem". OK, maybe the "official" name is different, but you get the concept. The problem is described as follows:


Problem:
Let us have an sequence/array of numbers [-1 , -2, 6 , 0, -4, 10, -3, -13, 1]. We want to find a subsequence of this array such that the sum of the numbers contained in the subsequence is no smaller than any other subsequence of numbers, meaning its sum is the maximum sum attainable by any subsequence in the array. For example, in the case above, the maximum subsequence is: [-1 , -2, (6 , 0, -4, 10), -3, -13, 1]  , from the third to the sixth items for a total sum of 12.


I want you to notice that if all numbers in the array are positive then obviously the maximum subsequence is the whole array itself. If all numbers are negative then an empty subsequence will have sum of zero and would be maximum. But suppose that you are not allowed to select an empty subsequence. So if all subsequences have negative sum then you have to select the one with the less negative sum. Well, today I am pasting code here that solves this problem.


Here you'll see three basic algorithms. One is the Brute Force algorithm that works in O(N^2) time, one is the Divide and Conquer algorithm that works in O(N logN), and the linear time algorithm that of course runs in O(N) time.


Here they go:


Brute Force:



int BruteForce(vector<int> A, int & start, int & end)
{
int max = 0;
bool first = true;
for(int i = 0; i < A.size(); i++)
{
int thisSubVal = 0;
for(int j = i; j < A.size(); j++)
{
thisSubVal += A[j];
if(thisSubVal > max || first)
{
max = thisSubVal;
start = i;
end = j;
first = false;
}
}
}
return max;
}

------------------------------


Divide and Conquer:



vector<int> FIND_MAX_CROSSING_SUBARRAY(vector<int> & A, int low, int mid, int high)
{
vector<int> tuple(3, 1);
int MAX_LEFT = 0;
int MAX_RIGHT = 1;
int MAX_SUM = 2;

int left_sum = 0;
int sum = 0;
bool first = true;
for(int i = mid; i >= low; i--)
{
sum += A[i];
if(sum > left_sum || first)
{
left_sum = sum;
tuple[MAX_LEFT] = i;
first = false;
}
}


int right_sum = 0;
sum = 0;
first = true;
for(int i = mid + 1; i <= high; i++)
{
sum += A[i];
if(sum > right_sum || first)
{
right_sum = sum;
tuple[MAX_RIGHT] = i;
first = false;
}
}
tuple[MAX_SUM] = left_sum + right_sum;
return tuple;
}


vector<int> FIND_MAXIMUM_SUBARRAY(vector<int> & A, int low, int high)
{
vector<int> tuple(3, 1);
int LEFT = 0;
int RIGHT = 1;
int MAX_SUM = 2;


if(low == high)
{
tuple[LEFT] = low;
tuple[RIGHT] = high;
tuple[MAX_SUM] = A[low];
return tuple;
}
else
{
int mid = (low + high) / 2;
vector<int> tupleLeft = FIND_MAXIMUM_SUBARRAY(A, low, mid);
vector<int> tupleRight = FIND_MAXIMUM_SUBARRAY(A, mid + 1, high);
vector<int> tupleCross = FIND_MAX_CROSSING_SUBARRAY(A, low, mid, high);


if(tupleLeft[MAX_SUM] >= tupleRight[MAX_SUM] && tupleLeft[MAX_SUM] >= tupleCross[MAX_SUM])
return tupleLeft;
else if(tupleRight[MAX_SUM] >= tupleLeft[MAX_SUM] && tupleRight[MAX_SUM] >= tupleCross[MAX_SUM])
return tupleRight;
else
return tupleCross;
}
}


int DivideAndConquer(vector<int> A, int & start, int & end)
{
vector<int> tuple = FIND_MAXIMUM_SUBARRAY(A, 0, A.size() - 1);
start = tuple[0];
end = tuple[1];
return tuple[2];
}

------------------------------
Linear:



int Linear(vector<int> A, int & start, int & end)
{
int size = A.size();
vector<int> P(size, 0);
vector<int> P_start(size, 0);
vector<int> P_end(size, 0);
P_start[0] = 0;
P_end[0] = 0;
int max = P[0] = A[0];
start = end = 0;
int sum = 0;
for(int j = 1; j < size; j++)
{
if(A[j] >= P[j-1] + A[j])
{
P[j] = A[j];
P_start[j] = j;
P_end[j] = j;
}
else
{
P[j] = P[j-1] + A[j];
P_start[j] = P_start[j-1];
P_end[j] = j;
}
if(P[j] >= max)
{
max = P[j];
start = P_start[j];
end = P_end[j];
}
}
return max;
}

------------------------------


So for all these functions just pass start and end as references and pass the array as an integer vector.


MArio