线性动态规划：最大子数组和问题的变种——允许至多删除一个元素的最大子数组和

题目描述

给定一个整数数组 nums，你可以至多删除一个元素（也可以不删除），然后需要找到具有最大和的连续子数组。返回这个最大的和。

示例：

• 输入：nums = [1, -2, 0, 3]
• 输出：4
• 解释：删除 -2，得到子数组 [1, 0, 3]，和为 4。

要求：

• 时间复杂度 O(n)，空间复杂度 O(n) 或更优。

解题思路

这是一个经典的最大子数组和问题（Kadane算法）的变种。其核心在于：当允许删除一个元素时，我们需要考虑“删除某个元素后，剩余部分的最大连续和”。这个问题可以通过动态规划来巧妙解决，其关键在于定义两个状态。

步骤1：问题分析与状态定义

传统的最大子数组和问题中，我们定义：

• dp[i]：以第 i 个元素结尾的最大子数组和。

在这个变种中，因为允许至多删除一个元素，所以我们需要区分“是否已经使用过删除权”。因此，我们定义两个状态数组：

• f[i]：表示以 nums[i] 结尾，且没有删除过任何元素的最大子数组和。
• g[i]：表示以 nums[i] 结尾，且已经删除过一个元素（删除的元素可以是 nums[i] 之前的某个元素，但不包括 nums[i] 自身）的最大子数组和。

注意： 因为子数组必须是连续的，所以删除操作只能删除当前考虑的子数组中的一个元素，但删除后剩余部分仍需连续。

步骤2：状态转移方程推导

我们逐个元素分析状态转移：

1. 对于 f[i]（没有删除过任何元素）：

   • 情况1：只取当前元素 nums[i]，单独作为一个子数组。
   • 情况2：将当前元素 nums[i] 接在以 nums[i-1] 结尾的未删除元素的子数组后面（即 f[i-1] + nums[i]）。
   • 取两者最大值：

     f[i] = max(nums[i], f[i-1] + nums[i])
     

   这与传统的 Kadane 算法转移方程完全一致。

2. 对于 g[i]（已经删除过一个元素）：
   这里有两种可能性：

   • 情况A：删除操作发生在 nums[i] 之前，并且我们选择保留 nums[i]。那么，以 nums[i] 结尾且已删除过元素的子数组，可以由 g[i-1]（在 nums[i-1] 结尾时已经删除过一个元素）接上 nums[i] 得到。

     候选值1 = g[i-1] + nums[i]
     

   • 情况B：删除操作就是删除 nums[i-1] 这个元素。那么，我们要的是以 nums[i-2] 结尾且没有删除过元素的子数组（即 f[i-2]），然后跳过 nums[i-1]，直接接上 nums[i]。

     候选值2 = f[i-2] + nums[i]   （当 i >= 2 时）
     

   • 取两者最大值。同时，我们还需要考虑一种特殊情况：如果 i == 1，那么删除 nums[0] 后，子数组就是 [nums[1]] 本身。

     当 i == 1 时： g[1] = nums[1] （因为删除 nums[0] 后，只剩下 nums[1]）
     当 i >= 2 时： g[i] = max(g[i-1] + nums[i], f[i-2] + nums[i])
     

   • 简化一下，可以写成：

     g[i] = nums[i] + max(g[i-1], f[i-2])   （当 i >= 2）
     

   注意，g[i] 的定义是“已经删除过一个元素”，所以它不能从 f[i-1]（未删除元素）直接转移过来，因为那样没有执行删除操作。

步骤3：初始化

• 初始时，考虑第一个元素 nums[0]：
  • f[0] = nums[0]：以 nums[0] 结尾，未删除任何元素的子数组就是它本身。
  • g[0] 需要特殊考虑。因为 g[i] 表示已经删除过一个元素，但当我们只考虑 nums[0] 这一个元素时，如果删除它，子数组就为空（和为0），但题目要求子数组非空吗？题目描述中“连续子数组”通常允许长度为0（和为0），但为了得到最大和，我们通常至少取一个元素。然而，对于 g[0] 的定义，它表示以 nums[0] 结尾且已经删除过一个元素，这是不可能的，因为只有一个元素时，如果删除它，就没有元素了。所以，我们可以将 g[0] 初始化为一个非常小的值（例如 -inf），表示无效状态。但在后续计算中，g[1] 会从“删除 nums[0]”这个有效操作开始。
    简便起见，我们可以初始化 g[0] = -inf，但实际编程中，我们可以从 i=1 开始计算 g[i]。

步骤4：计算与答案提取

我们遍历 i 从 0 到 n-1，计算 f[i] 和 g[i]。

• 最终答案并不是简单地取 f[n-1] 或 g[n-1]，因为最大和子数组可能以任何一个位置结尾，也可能不删除任何元素。
• 所以，最终答案是所有 f[i] 和 g[i] 中的最大值。
• 特别地，一个都不删除的情况已经被 f[i] 覆盖。

步骤5：举例演算

以 nums = [1, -2, 0, 3] 为例：

• 初始化：f[0] = 1。g[0] 我们暂时不赋予有效值，从 i=1 开始计算 g。
• i=1:
  • f[1] = max(-2, 1 + (-2)) = max(-2, -1) = -1
  • g[1]: 删除元素只能是 nums[0]，所以子数组为 [nums[1]] = [-2]，即 g[1] = -2。
• i=2:
  • f[2] = max(0, -1 + 0) = max(0, -1) = 0
  • g[2] = nums[2] + max(g[1], f[0]) = 0 + max(-2, 1) = 1
    解释：
    • 候选1 (g[1] + nums[2]): 已删除过元素（之前删了 nums[0]），子数组 [-2, 0] 和为 -2+0=-2? 等等，这里要注意，g[1] 表示以 nums[1] 结尾且已删除过元素的子数组和。我们之前算得 g[1] = -2 对应子数组 [-2]（删除 nums[0] 后）。那么 g[1] + nums[2] = -2 + 0 = -2 对应子数组 [-2, 0]（删除 nums[0] 后）。
    • 候选2 (f[0] + nums[2]): 删除 nums[1]，那么子数组为 [1, 0]，和为 1+0=1。
    • 所以 g[2] = max(-2, 1) = 1。
• i=3:
  • f[3] = max(3, 0 + 3) = 3
  • g[3] = nums[3] + max(g[2], f[1]) = 3 + max(1, -1) = 3 + 1 = 4
    解释：
    • 候选1 (g[2] + nums[3]): 之前已删除过元素（删除的是 nums[1]），子数组 [1, 0, 3] 和为 1+0+3=4。
    • 候选2 (f[1] + nums[3]): 删除 nums[2]，子数组 [1, -2, 3] 和为 1-2+3=2。
    • 所以 g[3] = max(4, 2) = 4。
• 所有 f 和 g 的值为：f: [1, -1, 0, 3]，g: [无效, -2, 1, 4]。
• 全局最大值是 max(1, -1, 0, 3, -2, 1, 4) = 4。

步骤6：算法实现与优化

我们可以用两个变量代替数组，将空间复杂度优化到 O(1)。

def maximumSum(arr):
    n = len(arr)
    if n == 0:
        return 0
    # 初始化
    f = arr[0]      # f[i-1]
    g = float('-inf') # g[i-1]，初始无效
    ans = arr[0]    # 全局最大值
    # 从 i=1 开始遍历
    for i in range(1, n):
        # 计算当前的 g[i]，注意 i>=2 时才考虑 f[i-2]，我们用 prev_f 记录 f[i-2]
        if i == 1:
            current_g = arr[i]  # 只能删除 arr[0]
        else:
            current_g = arr[i] + max(g, prev_f)
        # 计算当前的 f[i]
        current_f = max(arr[i], f + arr[i])
        # 更新答案
        ans = max(ans, current_f, current_g)
        # 为下一次迭代更新变量
        prev_f = f   # 这个 prev_f 实际上是 f[i-1]，在下一次循环中会变成 f[i-2]
        f = current_f
        g = current_g
    return ans

注意：prev_f 记录的是 f[i-2]。在循环开始时，对于 i=1，prev_f 还没有定义，所以 g[1] 单独处理。对于 i>=2，prev_f 就是 f[i-2]。

总结

这个问题的动态规划解法巧妙地将“是否使用删除权”作为状态维度，通过 f[i] 和 g[i] 分别跟踪，状态转移清晰地刻画了连续子数组在删除操作下的演变。最终，答案取所有状态的最大值，确保了最优解。此算法时间复杂度 O(n)，空间复杂度 O(1)，非常高效。