带限制的最大子数组和问题（允许最多删除一个元素）

题目描述

给定一个整数数组 nums，你可以在至多删除一个元素的情况下（也可以不删除任何元素），找出一个非空子数组（连续），使得其和最大。返回这个最大和。

示例1
输入：nums = [1, -2, 0, 3]
输出：4
解释：我们可以删除 -2，得到子数组 [1, 0, 3]，其和为 4。

示例2
输入：nums = [-1, -1, -1]
输出：-1
解释：删除任意一个元素后，子数组和最大为 -1（只取一个元素）。

问题理解

这是一个带操作限制的最大子数组和问题，允许在子数组中跳过（即删除）一个元素。它与经典的最大子数组和（Kadane算法）不同，因为我们可以有一次“豁免权”来跳过一个负数（或任意元素）以得到更大的和。直接贪心或简单扩展Kadane算法不够，需要用动态规划记录两种状态。

解题思路

我们将采用动态规划来解决，定义两个状态数组：

• dp0[i]：表示以 nums[i] 结尾，且没有删除任何元素的最大子数组和。
• dp1[i]：表示以 nums[i] 结尾，且已经删除了一个元素的最大子数组和。

我们需要考虑如何转移：

1. dp0[i]（没有删除过元素）：

   • 要么单独以 nums[i] 开始一个新子数组：nums[i]
   • 要么接在 dp0[i-1] 后面：dp0[i-1] + nums[i]
   • 转移方程：dp0[i] = max(nums[i], dp0[i-1] + nums[i])
   • 这和经典 Kadane 算法完全相同。

2. dp1[i]（已经删除过一个元素）：

   • 情况A：删除的元素是 nums[i] 之前的某个元素，并且 nums[i] 被保留。那么意味着在 i-1 之前已经删除过一个元素，所以继承 dp1[i-1] 并加上 nums[i]：dp1[i-1] + nums[i]
   • 情况B：删除的元素正好是 nums[i] 本身，那么 nums[i] 不被加入子数组，此时子数组以 i-1 结尾且没有删除过元素（因为删除操作用在当前元素上了），所以等于 dp0[i-1]
   • 转移方程：dp1[i] = max(dp1[i-1] + nums[i], dp0[i-1])
   • 注意：dp1[i] 可能从情况B得到，此时子数组实际上只到 i-1，但我们在定义上为了统一，仍让 dp1[i] 表示以 i 结尾（即使 nums[i] 被删除了，在子数组中不存在）。

3. 初始化：

   • dp0[0] = nums[0]
   • dp1[0] = 0？这里需要小心：dp1[0] 表示以 nums[0] 结尾，但已经删除过一个元素。要删除一个元素，至少需要两个元素，所以在只有一个元素时，不可能已经删除过一个元素。但为了统一，我们令 dp1[0] = -∞（不可达）。不过在实际计算中，我们可以用 0 表示“删除当前元素”的情况，但要注意避免从非法状态转移。一个安全做法是：
     dp1[0] = 0，表示删除 nums[0] 后得到一个空子数组？但题目要求非空子数组，所以不能从空转移。更严谨的是：
     令 dp0[0] = nums[0], dp1[0] = -inf（不可用）。
     然后对于 i ≥ 1，我们按上述转移。

4. 最终答案：

   • 最大子数组和可能来自任意结尾位置 i，且可能是 dp0[i]（没删除）或 dp1[i]（已删除）。所以答案是 max( max(dp0[i], dp1[i]) )，对所有 i。

详细步骤推导

我们以 nums = [1, -2, 0, 3] 为例，手动模拟：

1. 初始化
   dp0[0] = 1
dp1[0] = -∞（表示不可用）

2. i = 1, nums[1] = -2

   • dp0[1] = max(nums[1], dp0[0] + nums[1]) = max(-2, 1 + (-2)) = max(-2, -1) = -1
   • dp1[1]：
     • 情况A（之前已删除过元素）：dp1[0] + nums[1]，但 dp1[0] 不可用，忽略。
     • 情况B（删除当前元素 nums[1]）：dp0[0] = 1
       所以 dp1[1] = max(不可用, 1) = 1
   • 此时可能的子数组：
     • dp0[1] = -1 → 子数组 [1, -2]（没删除）
     • dp1[1] = 1 → 相当于删除了 nums[1]，子数组 [1]

3. i = 2, nums[2] = 0

   • dp0[2] = max(0, dp0[1] + 0) = max(0, -1) = 0
   • dp1[2]：
     • 情况A：dp1[1] + 0 = 1 + 0 = 1
     • 情况B：dp0[1] = -1
     • 取最大值：max(1, -1) = 1
   • 对应子数组：
     • dp0[2] = 0 → [0]
     • dp1[2] = 1 → 删除过某个元素，这里可以是删除 nums[1] 后的 [1, 0]

4. i = 3, nums[3] = 3

   • dp0[3] = max(3, dp0[2] + 3) = max(3, 0+3) = 3
   • dp1[3]：
     • 情况A：dp1[2] + 3 = 1 + 3 = 4
     • 情况B：dp0[2] = 0
     • 取最大值：max(4, 0) = 4
   • 对应子数组：
     • dp0[3] = 3 → [3]
     • dp1[3] = 4 → 删除 nums[1] 后的 [1, 0, 3]

5. 最终答案：所有 dp0[i] 和 dp1[i] 的最大值。
   dp0：[1, -1, 0, 3]，最大值 3
   dp1：[-∞, 1, 1, 4]，最大值 4
   所以最终最大和是 4。

边界情况与优化

• 全负数数组：如 [-1, -1, -1]
  模拟：

  • dp0[0] = -1
  • dp1[0] = -∞
  • i=1：dp0[1] = max(-1, -2) = -1, dp1[1] = max(不可用, -1) = -1（删除 nums[1] 得到子数组 [-1]）
  • i=2：dp0[2] = -1, dp1[2] = max(-1 + (-1) = -2, -1) = -1
    最大值为 max(-1, -1) = -1，符合预期（必须选一个元素）。

• 空间优化：我们只需要前一个状态的 dp0 和 dp1，所以可以用两个变量代替数组，将空间复杂度降至 O(1)。

• 初始化技巧：
  我们可以把 dp1[0] 设为 0，但在情况A转移时，只有 i ≥ 1 才可能从 dp1[i-1] 转移。更安全的是在循环中从 i=1 开始，并初始化 dp0_prev = nums[0], dp1_prev = 0（表示删除第一个元素得到的空子数组和为0，但在取最大值时不会影响，因为最终答案至少包含一个元素，我们会在比较中排除纯空子数组）。不过为了严谨，我们采用以下写法：

def maxSumAfterDeletion(nums):
    n = len(nums)
    if n == 1:
        return nums[0]
    
    dp0 = nums[0]      # 以当前位置结尾，没删除过
    dp1 = float('-inf') # 以当前位置结尾，删除过
    ans = nums[0]
    
    for i in range(1, n):
        # 注意：dp1_new 的转移中，dp0_prev 对应删除当前元素，dp1_prev 对应保留当前元素但之前删除过
        dp0_new = max(nums[i], dp0 + nums[i])
        dp1_new = max(dp1 + nums[i], dp0)   # 这里的 dp0 是旧的（即 dp0_prev）
        ans = max(ans, dp0_new, dp1_new)
        dp0, dp1 = dp0_new, dp1_new
    return ans

测试：

• [1, -2, 0, 3] → 4
• [-1, -1, -1] → -1
• [2, 1, -2, -5, 4] → 6（删除 -2 得 [2, 1, 4]）
• [1, 2, 3] → 6（不删除）

总结

这道题通过维护两个状态（是否已删除过元素）的DP，巧妙地处理了“至多删除一个元素”的限制。它的时间复杂度是 O(n)，空间复杂度 O(1)，是 Kadane 算法的一个自然扩展。理解状态转移的关键在于区分“删除操作发生在当前元素”还是“发生在之前”。