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;

}
 
}


darkmode