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