1388. Pizza With 3n Slices

题目信息

题号:

1388

难度:

Hard

主题:

动态规划、环形数组、非相邻选择

原题:

LeetCode 1388

重点:

圆形披萨有 3n 片,每轮选择一片后相邻两片被其他人拿走;最终恰好获得 n 片并最大化总大小

题目重述

给定长度为 3n 的环形数组 slices,表示披萨各片大小。每轮你选择一片,随后它左右相邻的两片分别被另外两人拿走,过程持续到披萨取完。

请返回你能够获得的 n 片披萨大小总和的最大值。该过程等价于在环形数组中选择 n 个互不相邻的元素。

1 <= n <= 166,1 <= slices[i] <= 1000。

自建示例

可以选择间隔一片的两个较大元素:

输入:slices = [1,2,3,4,5,6]
输出:10
解释:选择大小为 6 和 4 的两片,它们在环形位置上不相邻,总和为 10。

只有三片时只能获得一片:

输入:slices = [8,1,1]
输出:8
解释:选择最大的一片即可。