1388. Pizza With 3n Slices¶
题目信息¶
- 题号:
1388
- 难度:
Hard
- 主题:
动态规划、环形数组、非相邻选择
- 原题:
- 重点:
圆形披萨有
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
解释:选择最大的一片即可。