最大子数组和问题的变种——最多允许删除一个元素的最大子数组和

题目描述

给定一个整数数组 nums，可以最多删除一个元素（也可以不删除），要求找出具有最大和的连续子数组，并返回其和。

示例：
输入：nums = [1,-2,0,3]
输出：4
解释：删除元素 -2 后，子数组 [1,0,3] 的和为 4，这是最大的情况。

解题过程

这个问题是经典最大子数组和问题的变种，关键区别在于我们被允许最多删除一个元素。这意味着我们需要考虑两种情况：不删除任何元素的情况，以及恰好删除一个元素的情况。

步骤1：定义状态

我们需要记录两种信息：

• 以当前元素结尾且没有删除任何元素的最大子数组和
• 以当前元素结尾且已经删除了一个元素的最大子数组和

定义两个动态规划数组：

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

步骤2：状态转移方程

对于每个位置 i，我们考虑如何从 i-1 的状态转移到 i 的状态：

1. dp0[i] 的状态转移（没有删除过元素）：

   • 这个状态与经典最大子数组和问题相同
   • 我们可以将当前元素加入到前一个元素的子数组中，或者从当前元素重新开始
   • dp0[i] = max(dp0[i-1] + nums[i], nums[i])

2. dp1[i] 的状态转移（已经删除过一个元素）：
   这种情况有两种可能：

   • 我们在之前的位置已经删除过一个元素，现在只是将当前元素加入到已有的子数组中
   • 我们在当前位置删除元素，这意味着我们取之前位置（不删除任何元素）的最大子数组和

   因此：

   • dp1[i] = max(dp1[i-1] + nums[i], dp0[i-1])

步骤3：初始条件

• dp0[0] = nums[0]（第一个元素的最大子数组和就是它自己）
• dp1[0] = 0（对于第一个元素，如果删除它，子数组为空，和为0）

步骤4：计算过程

让我们通过示例 nums = [1,-2,0,3] 来演示：

i=0:

• dp0[0] = 1
• dp1[0] = 0

i=1:

• dp0[1] = max(dp0[0] + (-2), -2) = max(1-2, -2) = max(-1, -2) = -1
• dp1[1] = max(dp1[0] + (-2), dp0[0]) = max(0-2, 1) = max(-2, 1) = 1

i=2:

• dp0[2] = max(dp0[1] + 0, 0) = max(-1+0, 0) = max(-1, 0) = 0
• dp1[2] = max(dp1[1] + 0, dp0[1]) = max(1+0, -1) = max(1, -1) = 1

i=3:

• dp0[3] = max(dp0[2] + 3, 3) = max(0+3, 3) = 3
• dp1[3] = max(dp1[2] + 3, dp0[2]) = max(1+3, 0) = max(4, 0) = 4

步骤5：获取最终结果

最终答案是所有 dp0[i] 和 dp1[i] 中的最大值：

• 不删除任何元素的最大值：max(dp0) = max(1, -1, 0, 3) = 3
• 删除一个元素的最大值：max(dp1) = max(0, 1, 1, 4) = 4
• 最终结果：max(3, 4) = 4

步骤6：算法实现

def maximumSum(nums):
    if not nums:
        return 
    
    n = len(nums)
    if n == 1:
        return nums[0]
    
    dp0 = [0] * n  # 没有删除过元素
    dp1 = [0] * n  # 已经删除过一个元素
    
    dp0[0] = nums[0]
    dp1[0] = 0
    
    max_sum = max(dp0[0], dp1[0])
    
    for i in range(1, n):
        # 不删除任何元素的情况
        dp0[i] = max(dp0[i-1] + nums[i], nums[i])
        
        # 已经删除过一个元素的情况
        dp1[i] = max(dp1[i-1] + nums[i], dp0[i-1])
        
        # 更新最大值
        max_sum = max(max_sum, dp0[i], dp1[i])
    
    return max_sum

步骤7：空间优化

由于每个状态只依赖于前一个状态，我们可以使用变量而不是数组来节省空间：

def maximumSum(nums):
    if not nums:
        return 0
    
    n = len(nums)
    if n == 1:
        return nums[0]
    
    # 初始化
    dp0 = nums[0]  # 没有删除过元素
    dp1 = 0        # 已经删除过一个元素
    
    max_sum = max(dp0, dp1)
    
    for i in range(1, n):
        # 保存前一个状态
        prev_dp0 = dp0
        prev_dp1 = dp1
        
        # 更新当前状态
        dp0 = max(prev_dp0 + nums[i], nums[i])
        dp1 = max(prev_dp1 + nums[i], prev_dp0)
        
        # 更新最大值
        max_sum = max(max_sum, dp0, dp1)
    
    return max_sum

这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)（优化后版本）。