#include <bits/stdc++.h>

int memo(vector<int> &nums,int n,int ind,int taken, vector<vector<int>> &dp)
{
    if(ind<0)
        return 0;

    if(dp[taken][ind]!=-1)
        return dp[taken][ind];

    int ans=0;
    if(taken==0)
    {
        int x=nums[ind]+memo(nums,n,ind-1,1,dp);
        int y=memo(nums,n,ind-1,0,dp);
        ans=max(x,y);
    }
    else
        ans=memo(nums,n,ind-1,0,dp);


    dp[taken][ind]=ans;
    return ans;

}
int maximumNonAdjacentSum(vector<int> &nums)
{
    int n=nums.size();
    vector<vector<int>> dp(2,vector<int>(n,-1));
    return max(memo(nums,n,n-1,0,dp),memo(nums,n,n-1,1,dp));
}