# Max Sum without Adjacents

Given an array Arr of size N containing positive integers. Find the maximum sum of a subsequence such that no two numbers in the sequence should be adjacent in the array.

**Example 1:
Input:
N = 6
Arr[] = {5, 5, 10, 100, 10, 5}
Output: 110
Explanation: If you take indices 0, 3
and 5, then Arr[0]+Arr[3]+Arr[5] =
5+100+5 = 110.**

**
Example 2:
Input:
N = 4
Arr[] = {3, 2, 7, 10}
Output: 13
Explanation: 3 and 10 forms a non
continuous subsequence with maximum
sum.
**

**c++ implementation:**

**#include <iostream>
#include<algorithm>
using namespace std;
int main() {
int t;
cin>>t;
while(t--)
{
int n; cin>>n;
int a[n]; int excl=0;
int exclnew;
for(int i=0;i<n;i++)
cin>>a[i];
int incl=a[0];
for(int i=1;i<n;i++)
{
exclnew=max(incl,excl);
incl=excl+a[i];
excl=exclnew;
}
cout<<max(incl,excl)<<endl;
}
}**