Without Adjacent - Solution

Problem : Without Adjacent

Given an array arr[] of N positive integers. The task is to find a subsequence with maximum sum such that there should be no adjacent elements from the array in the subsequence.
Without Adjacent Contest

Hint

Input:
First line of input contains number of testcases T. For each testcase, first line of input contains size of array N. Next line contains N elements of the array space seperated.

Output:
For each testcase, print the maximum sum of the subsequence.

Constraints:
1 <= T <= 100
1 <= N <= 106
1 <= arr[i] <= 106

Example:
Input:
2
3
1 2 3
3
1 20 3

Output:
4
20

Explanation:
Testcase 1: Elements 1 and 3 form a subsequence with maximum sum and no elements in the subsequence are adjacent in the array.
Testcase 2: Element 20 from the array forms a subsequence with maximum sum.

Solution:

 #include <bits/stdc++.h>
using namespace std;

int main() {
    //code
    int T;
    cin>>T;
    while(T--){
        int N;
        cin>>N;
        
        int array[N];
        
        for(int i=0; i<N; i++){
            cin>>array[i];
        }
        
        long long include = array[0];
        long long exclude = 0;
        long long excl;
        
        for (int i=1; i<N; i++){
            excl = (include>exclude) ? include : exclude;
            include = exclude + array[i];
            exclude = excl;
        }
        
        cout<<((include > exclude) ? include : exclude)<<endl;
    }
    return 0;
}