Max Sum

Given an array of positive numbers, find the maximum sum of a sub-sequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.

Input:

The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is N,N is the size of array.
The second line of each test case contains N input C[i].

Output:

Print the maximum sum of a sub-sequence.

 

C++ Solution


#include <iostream>
#include <vector>

using namespace std;

/*
T denotes maxsum then
T(N) = max(A[N-1] + T(N-2), T(N-1))
*/
void printMaxSum(vector <int> inp)
{
int size = inp.size();
vector <int> maxSum;
if(size <= 0)
return;
else
{
if(size == 1)
{
cout<<inp[0]<<endl;
return;
}
else
{
maxSum.push_back(inp[0]);
maxSum.push_back(max(inp[0],inp[1]));
}
}
for(int i = 2; i < size; i++)
{
int included = inp[i] + maxSum[i - 2];
int excluded = maxSum[i-1];
maxSum.push_back(max(included,excluded));
}
cout<< maxSum[size-1]<<endl;
}

int main() {
int T = 0;
//read number of test cases
cin>>T;
vector < vector <int> > allInputs;
for (int i = 0; i < T; i++)
{
int N = 0;
cin>>N;
//read all N inputs in a vector
vector <int> arr;
for(int j = 0; j < N; j++)
{
int inp = 0;
cin>>inp;
arr.push_back(inp);
}
allInputs.push_back(arr);
}

for(int i = 0; i < T; i++)
{
printMaxSum(allInputs[i]);
}

return 0;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s