//This was my Solution
long long findMaxSubsetSum(int N, vector<int> &A) {
        // code here
        pair<long long,long long> prev, curr;
        if(N == 1)
            return A[0];
        prev = {A[N-1] , 0};
        for(int i = N - 2; i >= 0 ; i--){
            curr.first = max(A[i]+ prev.first, A[i] + prev.second);
            curr.second = prev.first;
            prev = curr;
        }
        return max(curr.first, curr.second);
        
    }
    //This is others solution
  // recursive -> O(2^n)
long long recursive_approach(vector<int>&arr,int index,int n){
    if(index>=n){
        return 0;
    }

    long long take,notTake;

    take=arr[index]+recursive_approach(arr,index+1,n);
    notTake=(index+1>=n?0:arr[index+1]+ recursive_approach(arr,index+2,n));

    return max(take,notTake);
}
 //memoized -> O(n), Space->O(n)
long long memoization_approach(vector<int>&arr,int index,int n,vector<int>&t){
    if(index>=n){
        return 0;
    }

    long long take,notTake;

    if(t[index]!=-1){
        return t[index];
    }

    take=arr[index]+memoization_approach(arr,index+1,n,t);
    notTake=(index+1>=n?0:arr[index+1]+ memoization_approach(arr,index+2,n,t));

    return t[index]=max(take,notTake);
}
//tabulation -> O(n), O(n)
long long tabulation_approach(vector<int>&arr,int n){
    vector<int>t(n+2,0);
    long long take,notTake;
    for(int i=n-1;i>=0;i--){
        take=arr[i]+t[i+1];
        notTake=(i+1>=n?0:arr[i+1]+t[i+2]);
        t[i]=max(take,notTake);
    }
    return t[0];
}
//optimal -> O(n) , O(1)
long long spaceOptimized_approach(vector<int>&arr,int n){
    long long take,notTake,prev_1,prev_2;
    prev_1=0;
    prev_2=0;

    for(int i=n-1;i>=0;i--){
        take=arr[i]+prev_1;
        notTake=(i+1>=n?0:arr[i+1]+prev_2);
        prev_2=prev_1;
        prev_1=max(take,notTake);
    }

    return prev_1;
}