Medium

题目描述

给你一个整数数组 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 <= 2000
  • 1 <= nums[i] <= 1000

解题思路

这是一道动态规划问题，核心思路如下：

  1. 关键观察：第一次操作确定了所有后续操作的分数。因为题目要求所有操作必须有相同的分数，所以我们只需要考虑三种可能的分数：

    • nums[0] + nums[1]（删除前两个）
    • nums[n-2] + nums[n-1]（删除后两个）
    • nums[0] + nums[n-1]（删除首尾）

  2. 动态规划设计：对于每个可能的分数，使用 dp[l][r] 表示在子数组 nums[l...r] 上能执行的最大操作数。

  3. 状态转移：对于区间 [l, r]，尝试三种操作：

    • 删除 nums[l], nums[l+1]：如果和等于目标分数，则 dp[l][r] = 1 + dp[l+2][r]
    • 删除 nums[r-1], nums[r]：如果和等于目标分数，则 dp[l][r] = 1 + dp[l][r-2]
    • 删除 nums[l], nums[r]：如果和等于目标分数，则 dp[l][r] = 1 + dp[l+1][r-1]

  4. 边界条件：当 l >= r 时，无法进行操作，返回 0。

使用记忆化搜索来避免重复计算，最终答案是三种可能分数下的最大操作数。

代码实现

class Solution {
public:
    int maxOperations(vector<int>& nums) {
        int n = nums.size();
        
        function<int(int, int, int, vector<vector<int>>&)> dfs = [&](int l, int r, int target, vector<vector<int>>& memo) -> int {
            if (l >= r) return 0;
            if (memo[l][r] != -1) return memo[l][r];
            
            int res = 0;
            // 删除前两个
            if (l + 1 <= r && nums[l] + nums[l + 1] == target) {
                res = max(res, 1 + dfs(l + 2, r, target, memo));
            }
            // 删除后两个
            if (l <= r - 1 && nums[r - 1] + nums[r] == target) {
                res = max(res, 1 + dfs(l, r - 2, target, memo));
            }
            // 删除首尾
            if (nums[l] + nums[r] == target) {
                res = max(res, 1 + dfs(l + 1, r - 1, target, memo));
            }
            
            return memo[l][r] = res;
        };
        
        int ans = 0;
        // 尝试三种可能的分数
        vector<int> targets = {nums[0] + nums[1], nums[n-2] + nums[n-1], nums[0] + nums[n-1]};
        
        for (int target : targets) {
            vector<vector<int>> memo(n, vector<int>(n, -1));
            ans = max(ans, dfs(0, n - 1, target, memo));
        }
        
        return ans;
    }
};

class Solution:
    def maxOperations(self, nums: List[int]) -> int:
        n = len(nums)
        
        def dfs(l, r, target, memo):
            if l >= r:
                return 0
            if memo[l][r] != -1:
                return memo[l][r]
            
            res = 0
            # 删除前两个
            if l + 1 <= r and nums[l] + nums[l + 1] == target:
                res = max(res, 1 + dfs(l + 2, r, target, memo))
            # 删除后两个
            if l <= r - 1 and nums[r - 1] + nums[r] == target:
                res = max(res, 1 + dfs(l, r - 2, target, memo))
            # 删除首尾
            if nums[l] + nums[r] == target:
                res = max(res, 1 + dfs(l + 1, r - 1, target, memo))
            
            memo[l][r] = res
            return res
        
        ans = 0
        # 尝试三种可能的分数
        targets = [nums[0] + nums[1], nums[n-2] + nums[n-1], nums[0] + nums[n-1]]
        
        for target in targets:
            memo = [[-1] * n for _ in range(n)]
            ans = max(ans, dfs(0, n - 1, target, memo))
        
        return ans

public class Solution {
    public int MaxOperations(int[] nums) {
        int n = nums.Length;
        
        int Dfs(int l, int r, int target, int[,] memo) {
            if (l >= r) return 0;
            if (memo[l, r] != -1) return memo[l, r];
            
            int res = 0;
            // 删除前两个
            if (l + 1 <= r && nums[l] + nums[l + 1] == target) {
                res = Math.Max(res, 1 + Dfs(l + 2, r, target, memo));
            }
            // 删除后两个
            if (l <= r - 1 && nums[r - 1] + nums[r] == target) {
                res = Math.Max(res, 1 + Dfs(l, r - 2, target, memo));
            }
            // 删除首尾
            if (nums[l] + nums[r] == target) {
                res = Math.Max(res, 1 + Dfs(l + 1, r - 1, target, memo));
            }
            
            return memo[l, r] = res;
        }
        
        int ans = 0;
        // 尝试三种可能的分数
        int[] targets = {nums[0] + nums[1], nums[n-2] + nums[n-1], nums[0] + nums[n-1]};
        
        foreach (int target in targets) {
            int[,] memo = new int[n, n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    memo[i, j] = -1;
                }
            }
            ans = Math.Max(ans, Dfs(0, n - 1, target, memo));
        }
        
        return ans;
    }
}

var maxOperations = function(nums) {
    const n = nums.length;
    
    function dfs(l, r, target, memo) {
        if (l >= r) return 0;
        if (memo[l][r] !== -1) return memo[l][r];
        
        let res = 0;
        // 删除前两个
        if (l + 1 <= r && nums[l] + nums[l + 1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n²)每种可能的分数需要 O(n²) 时间进行记忆化搜索，共3种可能
空间复杂度O(n²)记忆化数组的空间开销