Untitled

 avatar
unknown
plain_text
a year ago
377 B
1
Indexable
#include <bits/stdc++.h> 

int solve(vector<int> &nums,int i,vector<int> &dp){

    if(i>=nums.size()) return 0;
    if(dp[i]!=-1) return dp[i];

    int ans=max(solve(nums,i+1,dp),solve(nums,i+2,dp)+nums[i]);
    dp[i]=ans;
    return ans;
}

int maximumNonAdjacentSum(vector<int> &nums){
    
    vector<int> dp(nums.size(),-1);
    return solve(nums,0,dp);
}