Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
752 B
1
Indexable
Never
class Solution { //01 knapsack
public:
    int solve(int i,int end,vector<int>&slices,int n,vector<vector<int>>&dp){ // n -no of slices i can take
        if(n==0 || i>end) return 0;
        
        if(dp[i][n]!=-1) return dp[i][n];

        int include= slices[i] +solve(i+2,end,slices,n-1,dp);
        int exclude= solve(i+1,end,slices,n,dp);
        return dp[i][n]=max(include,exclude);

    }

    int maxSizeSlices(vector<int>& slices) {
        int n=slices.size();

        vector<vector<int>> dp(n,vector<int>(n,-1));
        vector<vector<int>> dp2(n,vector<int>(n,-1));

        int c1=solve(0,slices.size()-2,slices,n/3,dp);
        int c2=solve(1,slices.size()-1,slices,n/3,dp2);
        return max(c1,c2);
    }
};