_1388.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.Arrays;

publicclass_1388 {
publicstaticclassSolution1 {
publicintmaxSizeSlices(int[] slices) {
intn = slices.length;
int[] b = Arrays.copyOf(slices, 2 * n);
for (inti = 0; i < n; i++) {
b[i + n] = slices[i];
 }
int[][] dp = newint[2 * n][2 * n];
for (intlen = 3; len <= n; len += 3) {
for (inti = 0; i + len - 1 < 2 * n; i++) {
intj = i + len - 1;
for (intk = i + 3; k <= j - 2; k += 3) {
dp[i][j] = Math.max(dp[i][j], dp[i][k - 1] + dp[k][j]);
 }
for (intk = i + 1; k < j; k += 3) {
dp[i][j] =
Math.max(
dp[i][j],
 (i + 1 <= k - 1 ? dp[i + 1][k - 1] : 0)
 + b[k]
 + (k + 1 <= j - 1 ? dp[k + 1][j - 1] : 0));
 }
 }
 }
intans = 0;
for (inti = 0; i < n; i++) {
ans = Math.max(ans, dp[i][i + n - 1]);
 }
returnans;
 }
 }
}