LeetCode 题解工作台
相同分数的最大操作数目 II
给你一个整数数组 nums ，如果 nums 至少 包含 2 个元素，你可以执行以下操作中的 任意 一个： 选择 nums 中最前面两个元素并且删除它们。 选择 nums 中最后两个元素并且删除它们。 选择 nums 中第一个和最后一个元素并且删除它们。 一次操作的 分数 是被删除元素的和。 在确保…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
分数 的取值有三种情况，分别是 $s = nums[0] + nums[1]$, $s = nums[0] + nums[n-1]$, $s = nums[n-1] + nums[n-2]$。我们可以针对这三种情况，分别进行记忆化搜索。 我们设计一个函数 $dfs(i, j)$，表示在分数为 的情况下，从下标 到下标 的最大操作次数。函数 $dfs(i, j)$ 的执行过程如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数数组 nums ，如果 nums 至少 包含 2 个元素，你可以执行以下操作中的 任意 一个：
- 选择
nums中最前面两个元素并且删除它们。 - 选择
nums中最后两个元素并且删除它们。 - 选择
nums中第一个和最后一个元素并且删除它们。
一次操作的 分数 是被删除元素的和。
在确保 所有操作分数相同 的前提下，请你求出 最多 能进行多少次操作。
请你返回按照上述要求 最多 可以进行的操作次数。
示例 1：
输入：nums = [3,2,1,2,3,4] 输出：3 解释：我们执行以下操作： - 删除前两个元素，分数为 3 + 2 = 5 ，nums = [1,2,3,4] 。 - 删除第一个元素和最后一个元素，分数为 1 + 4 = 5 ，nums = [2,3] 。 - 删除第一个元素和最后一个元素，分数为 2 + 3 = 5 ，nums = [] 。 由于 nums 为空，我们无法继续进行任何操作。
示例 2：
输入：nums = [3,2,6,1,4] 输出：2 解释：我们执行以下操作： - 删除前两个元素，分数为 3 + 2 = 5 ，nums = [6,1,4] 。 - 删除最后两个元素，分数为 1 + 4 = 5 ，nums = [6] 。 至多进行 2 次操作。
提示：
2 <= nums.length <= 20001 <= nums[i] <= 1000
解题思路
方法一：记忆化搜索
分数 的取值有三种情况，分别是 , , 。我们可以针对这三种情况，分别进行记忆化搜索。
我们设计一个函数 ，表示在分数为 的情况下，从下标 到下标 的最大操作次数。函数 的执行过程如下：
- 如果 ，表示区间 的长度小于 ，无法进行任何操作，返回 。
- 如果 ，表示可以删除下标 和下标 的元素，此时最大操作次数为 。
- 如果 ，表示可以删除下标 和下标 的元素，此时最大操作次数为 。
- 如果 ，表示可以删除下标 和下标 的元素，此时最大操作次数为 。
- 返回以上的最大值即可。
最后，我们分别计算三种情况的最大操作次数，取最大值返回即可。
时间复杂度 ，空间复杂度 。其中 是数组 的长度。
class Solution:
def maxOperations(self, nums: List[int]) -> int:
@cache
def dfs(i: int, j: int, s: int) -> int:
if j - i < 1:
return 0
ans = 0
if nums[i] + nums[i + 1] == s:
ans = max(ans, 1 + dfs(i + 2, j, s))
if nums[i] + nums[j] == s:
ans = max(ans, 1 + dfs(i + 1, j - 1, s))
if nums[j - 1] + nums[j] == s:
ans = max(ans, 1 + dfs(i, j - 2, s))
return ans
n = len(nums)
a = dfs(2, n - 1, nums[0] + nums[1])
b = dfs(0, n - 3, nums[-1] + nums[-2])
c = dfs(1, n - 2, nums[0] + nums[-1])
return 1 + max(a, b, c)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexity depends on the DP implementation. A naive recursive approach may reach O(2^n), but memoization reduces repeated state computations. With optimized DP, expect time O(n^3) in worst case and space O(n^2) for storing subarray results. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focus on state transition dynamic programming with memoization to avoid redundant calculations.
- question_mark
Consider how pair selection order affects maximum operations with the same score.
- question_mark
Highlight that after choosing the first operation, the score of subsequent operations is fixed and drives DP decisions.
常见陷阱
外企场景- error
Forgetting to fix the score after the first operation, leading to inconsistent totals.
- error
Not using memoization, which causes timeouts on larger arrays.
- error
Assuming any pair sum works without verifying it maintains the same score across all operations.
进阶变体
外企场景- arrow_right_alt
Allow operations that remove more than two elements while keeping the score consistent.
- arrow_right_alt
Count the maximum operations but with a limited number of total deletions.
- arrow_right_alt
Extend to arrays with negative integers and track valid operation sequences.