# 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<<endl;
return;
}
else
{
maxSum.push_back(inp);
maxSum.push_back(max(inp,inp));
}
}
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