题目描述

给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨：

• 你挑选 任意  一块披萨。

• Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。

• Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。

• 重复上述过程直到没有披萨剩下。

每一块披萨的大小按顺时针方向由循环数组 slices 表示。

请你返回你可以获得的披萨大小总和的最大值。

样例

输入：slices = [1,2,3,4,5,6]
输出：10
解释：选择大小为 4 的披萨，Alice 和 Bob 分别挑选大小为 3 和 5 的披萨。然后你选择大小为 6 的披萨，
Alice 和 Bob 分别挑选大小为 2 和 1 的披萨。你获得的披萨总大小为 4 + 6 = 10 。

输入：slices = [8,9,8,6,1,1]
输出：16
解释：两轮都选大小为 8 的披萨。如果你选择大小为 9 的披萨，
你的朋友们就会选择大小为 8 的披萨，这种情况下你的总和不是最大的。

输入：slices = [4,1,2,5,8,3,1,9,7]
输出：21

输入：slices = [3,1,2]
输出：3

提示：

• 1 <= slices.length <= 500

• slices.length % 3 == 0

• 1 <= slices[i] <= 1000

算法分析

问题可以转化为：从 n个披萨中去n / 3块不相邻的披萨的大小总和的最大值

• 1、从 1 到 n - 1 个披萨中选n / 3个，得到的最大值是res1

• 2、从 2 到 n 个披萨中选n / 3个，得到的最大值是res2

• 3、取res1，res2的最大值

时间复杂度 $O(n ^ 2)$

Java 代码

class Solution {
    static int N = 510;
    static int[][] f = new int[N][N];
    static int[][] g = new int[N][N];
    static int[] w = new int[N];
    public int maxSizeSlices(int[] slices) {
        int n = slices.length;
        for(int i = 1;i <= n;i ++) w[i] = slices[i - 1];
        for(int i = 1;i <= n;i ++) 
        {
            Arrays.fill(f[i],0);
            Arrays.fill(g[i],0);
        }
        f[1][1] = w[1];
        for(int i = 2;i <= n - 1;i ++)
        {
            for(int j = 1;j <= n / 3;j ++)
            {
                f[i][j] = Math.max(f[i - 1][j],f[i - 2][j - 1] + w[i]);
            }
        }
        for(int i = 2;i <= n;i ++)
        {
            for(int j = 1;j <= n / 3;j ++)
            {
                g[i][j] = Math.max(g[i - 1][j],g[i - 2][j - 1] + w[i]);
            }
        }
        return Math.max(f[n - 1][n / 3],g[n][n / 3]);
    }
}