相同分数的最大操作数目 II

难度: 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

Submission

运行时间: 32 ms

内存: 17.4 MB


class Solution:
    def maxOperations(self, nums: List[int]) -> int:
        
        n=len(nums)

        
        start=0
        end=n
        l=nums[0]+nums[1]
        m=nums[0]+nums[-1]
        r=nums[-2]+nums[-1]
        @cache
        def dfs(i,j,target):
            if i>=j-1:
                return 0
            ma=0
            l=nums[i]+nums[i+1]
            m=nums[i]+nums[j-1]
            r=nums[j-2]+nums[j-1]
            if j-i>=4 and nums[i]+nums[i+1]==nums[j-1]+nums[j-2]==target:
                ma=max(ma,dfs(i+2,j-2,target)+2)
            else:
                if l==target:
                    ma=max(ma,dfs(i+2,j,target)+1)
                    
                if m==target:
                    ma=max(ma,dfs(i+1,j-1,target)+1)
                    
                if r==target:
                    ma=max(ma,dfs(i,j-2,target)+1)
            return ma
        ans1=dfs(start+2,end,l)
        ans2=dfs(start+1,end-1,m)
        ans3=dfs(start,end-2,r)

        return max(ans1,ans2,ans3)+1

Explain

该题解采用的是深度优先搜索 (DFS) 递归方法，结合记忆化来解决问题。首先，计算出从数组开始两个元素、最后两个元素以及第一个和最后一个元素的和。然后，对这三种操作的每种初始和，使用DFS来尝试所有可能的删除操作，以保证每次操作的得分相同。DFS 函数检查当前的子数组边界，尝试所有可能的删除操作，并递归地寻找最多的操作次数。最后，返回三种初始和操作中，得到的最大操作次数。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

class Solution:
    def maxOperations(self, nums: List[int]) -> int:
        n = len(nums)
        start = 0
        end = n
        l = nums[0] + nums[1]
        m = nums[0] + nums[-1]
        r = nums[-2] + nums[-1]
        @cache
        def dfs(i, j, target):
            if i >= j - 1:
                return 0
            ma = 0
            l = nums[i] + nums[i + 1]
            m = nums[i] + nums[j - 1]
            r = nums[j - 2] + nums[j - 1]
            if j - i >= 4 and nums[i] + nums[i + 1] == nums[j - 1] + nums[j - 2] == target:
                ma = max(ma, dfs(i + 2, j - 2, target) + 2)
            else:
                if l == target:
                    ma = max(ma, dfs(i + 2, j, target) + 1)
                if m == target:
                    ma = max(ma, dfs(i + 1, j - 1, target) + 1)
                if r == target:
                    ma = max(ma, dfs(i, j - 2, target) + 1)
            return ma
        ans1 = dfs(start + 2, end, l)
        ans2 = dfs(start + 1, end - 1, m)
        ans3 = dfs(start, end - 2, r)
        return max(ans1, ans2, ans3) + 1

Explore

在DFS递归函数中，递归终止条件是确保递归过程能在合适的时机停止，从而避免无效或无限递归。选择'i >= j - 1'作为停止条件是因为，当i和j指向的元素位置重合或者i超过j时，子数组中已经没有足够的元素来进行任何操作。具体地，当i等于j-1时，子数组只剩下一个元素，无法形成有效的操作对；当i大于j-1时，子数组没有元素，同样无法进行操作。因此，这个条件确保只有在子数组至少有两个元素时，递归才继续执行。

记忆化是一种优化技术，用于存储已经计算过的结果，以避免重复计算，从而提高算法的效率。在Python中，记忆化可以通过使用@cache装饰器实现，该装饰器是标准库functools中的一部分。在DFS函数上应用@cache装饰器后，函数的每次调用结果都会被存储起来。当递归遇到相同的参数时，不需要重新计算，直接从缓存中取出结果。这大大减少了重复计算，尤其是在处理具有大量重复子问题的递归问题时，如本题中的多种可能的删除操作。因此，@cache能显著提高性能，尤其是在深度递归和大数据集处理时。

当同时满足四元素边界条件，即子数组的前两个元素之和等于后两个元素之和且等于目标值时，选择同时删除这四个元素是基于最大化操作数的考虑。通过同时删除这两对元素，我们可以确保这一步操作是有效的，且直接增加了两次操作数（即+2），这是在给定条件下可获得的最大操作增量。这种策略优先考虑删除更多元素的操作，旨在尽可能多地执行有效操作，从而最大化总操作数。这种选择反映了在保证操作有效的同时，尽可能多地减少数组中的元素数量，以便为后续操作留下更多的可能性。