1
class Solution {
2
 public:
3
  int dp[501][501];
4

5
  int solve(vector<int> &v, int i, int count) {
6
    if (i >= v.size() || count > v.size() / 3) return 0;
7

8
    if (dp[i][count] != -1) return dp[i][count];
9

10
    int pick = v[i] + solve(v, i + 2, count + 1);
11
    int notPick = solve(v, i + 1, count);
12

13
    return dp[i][count] = max(pick, notPick);
14
  }
15

16
  int maxSizeSlices(vector<int> &slices) {
17
    vector<int> v1;
18
    vector<int> v2;
19

20
    for (int i = 0; i < slices.size(); i++) {
21
      if (i != slices.size() - 1) v1.push_back(slices[i]);
22
      if (i != 0) v2.push_back(slices[i]);
23
    }
24
    memset(dp, -1, sizeof(dp));
25
    int ans1 = solve(v1, 0, 0);
26
    memset(dp, -1, sizeof(dp));
27
    int ans2 = solve(v2, 0, 0);
28

29
    return max(ans1, ans2);
30
  }
31
};