线性动态规划：最大子数组和（允许删除一个元素）

题目描述
给定一个整数数组nums，你可以最多从数组中删除一个元素（也可以不删除），请计算并返回可能的最大子数组和。

示例1：
输入：nums = [1,-2,0,3]
输出：4
解释：删除-2后，子数组[1,0,3]的和为4

示例2：
输入：nums = [1,-2,-2,3]
输出：3
解释：删除第一个-2，子数组[1,-2,3]的和为2；删除第二个-2，子数组[1,-2,3]的和为2；不删除任何元素，子数组[3]的和为3

解题过程

步骤1：理解问题本质
这个问题是经典最大子数组和问题的变种，关键区别在于我们被允许删除数组中的一个元素。这意味着我们需要考虑两种情况：

1. 不删除任何元素时的最大子数组和
2. 删除某个元素时的最大子数组和

步骤2：定义状态
我们使用动态规划来解决这个问题，定义两个状态数组：

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

步骤3：状态转移方程

对于dp_no_delete[i]（没有删除的情况）：

• 如果dp_no_delete[i-1] > 0，那么dp_no_delete[i] = dp_no_delete[i-1] + nums[i]
• 否则dp_no_delete[i] = nums[i]
  即：dp_no_delete[i] = max(dp_no_delete[i-1] + nums[i], nums[i])

对于dp_with_delete[i]（已经删除一个元素的情况），这里有两种可能性：

1. 删除当前元素nums[i]：那么结果就是dp_no_delete[i-1]（因为当前元素被删除了）
2. 在之前已经删除了某个元素：那么结果就是dp_with_delete[i-1] + nums[i]

因此：dp_with_delete[i] = max(dp_no_delete[i-1], dp_with_delete[i-1] + nums[i])

步骤4：初始化

• dp_no_delete[0] = nums[0]（第一个元素）
• dp_with_delete[0] = 0（删除第一个元素，子数组为空，和为0）

步骤5：计算过程示例

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

i=0：

• dp_no_delete[0] = 1
• dp_with_delete[0] = 0

i=1：

• dp_no_delete[1] = max(1 + (-2), -2) = max(-1, -2) = -1
• dp_with_delete[1] = max(dp_no_delete[0], dp_with_delete[0] + (-2)) = max(1, 0-2) = max(1, -2) = 1

i=2：

• dp_no_delete[2] = max(-1 + 0, 0) = max(-1, 0) = 0
• dp_with_delete[2] = max(dp_no_delete[1], dp_with_delete[1] + 0) = max(-1, 1+0) = max(-1, 1) = 1

i=3：

• dp_no_delete[3] = max(0 + 3, 3) = max(3, 3) = 3
• dp_with_delete[3] = max(dp_no_delete[2], dp_with_delete[2] + 3) = max(0, 1+3) = max(0, 4) = 4

步骤6：获取最终结果
最终结果是所有dp_no_delete[i]和dp_with_delete[i]中的最大值。

对于上面的例子：max(1, -1, 0, 3, 0, 1, 1, 4) = 4

步骤7：算法实现

def maximumSum(arr):
    n = len(arr)
    if n == 0:
        return 0
    if n == 1:
        return arr[0]
    
    dp_no_delete = [0] * n
    dp_with_delete = [0] * n
    
    dp_no_delete[0] = arr[0]
    dp_with_delete[0] = 0
    
    result = max(dp_no_delete[0], dp_with_delete[0])
    
    for i in range(1, n):
        dp_no_delete[i] = max(dp_no_delete[i-1] + arr[i], arr[i])
        dp_with_delete[i] = max(dp_no_delete[i-1], dp_with_delete[i-1] + arr[i])
        result = max(result, dp_no_delete[i], dp_with_delete[i])
    
    return result

步骤8：复杂度分析

• 时间复杂度：O(n)，只需要遍历数组一次
• 空间复杂度：O(n)，使用两个长度为n的数组。可以通过滚动数组优化到O(1)

步骤9：边界情况考虑

• 空数组：返回0
• 单元素数组：返回该元素
• 全负数数组：返回最大的单个元素
• 全正数数组：返回所有元素之和（不删除任何元素）