题目描述

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

• 你挑选 任意 一块披萨。
• Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
• Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
• 重复上述过程直到没有披萨剩下。

每一块披萨的大小按顺时针方向由循环数组 slices 表示。
请你返回你可以获得的披萨大小总和的最大值。

样例1

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

样例2

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

样例3

输入：nums = [0]
输出：0

提示

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

算法1

(动态规划)

• 题意可以转换为从一个3n的环形序列中恰好选不相邻的n个元素能获得的最大价值，类似LeetCode213.打家劫舍 II

• 环形结构说明第一块披萨和最后一块披萨连在一起，不能同时取；所以我们对数组进行两次扫描，最后取结果中较大的即可：

  1. 把数组的第一个元素删掉，表示不拿第一块披萨
  2. 把数组的最后一个元素删掉，表示不拿最后一块披萨

• 状态表示：f[i][j]表示前i块披萨中，恰好拿j块披萨能得到的最大价值

• 状态转移：f[i][j] = max(f[i-1][j], f[i-2][j-1] + nums[i-1])

  1. 如果不拿第i块披萨，则取前i-1块披萨能获得的最大值
  2. 如果拿第i块披萨，则第i-1块披萨不能拿，取前i-2块披萨能获得的最大价值加上当前这块披萨的金额

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

• 空间复杂度：$O(n^2)$

Java 代码

class Solution {
    public int maxSizeSlices(int[] slices) {
        int n = slices.length;
        int[] a = Arrays.copyOfRange(slices, 0, n - 1);
        int[] b = Arrays.copyOfRange(slices, 1, n);
        return Math.max(solve(a), solve(b));
    }

    int solve(int[] nums){
        int n = nums.length;
        int m = (n + 1) / 3;
        // f[i][j]: 前i块披萨中选j块的最大值
        int[][] f = new int[n + 1][m + 1];
        f[1][1] = nums[0];
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= m; j++){
                f[i][j] = Math.max(f[i-1][j], f[i-2][j-1] + nums[i-1]);
            }
        }
        return f[n][m];
    }
}