//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; }