线性动态规划：删除一次得到子数组最大和

问题描述

给定一个整数数组 arr，你可以从数组中删除一个连续子数组（也可以不删除任何元素），使得剩下的元素构成的新数组的和最大。你需要返回这个可能的最大和。

注意：子数组是原始数组中的一个连续子序列。删除一个子数组后，原始数组的剩余元素会保持其原始顺序，拼接成一个新数组。

示例 1：
输入：arr = [1,-2,0,3]
输出：4
解释：我们可以删除子数组 [-2]，这样剩下的元素是 [1,0,3]，和为 4。

示例 2：
输入：arr = [1,-2,-2,3]
输出：3
解释：我们直接删除子数组 [-2,-2]，剩下的元素是 [1,3]，和为 3。

示例 3：
输入：arr = [-1,-1,-1,-1]
输出：-1
解释：删除一个元素后，剩下的元素至少有一个，所以必须保留一个 -1，和为 -1。

限制：

• 1 <= arr.length <= 10^5
• -10^4 <= arr[i] <= 10^4

解题思路

这个问题是“最大子数组和”的一个变种。在经典的最大子数组和问题中，我们只能选择连续子数组。而这里允许我们先删除一个连续子数组，再从剩下的元素中求总和。这等价于：从原数组中选取两个不重叠的连续子数组，将它们加起来，使得和最大。但这两个子数组之间的部分就是我们要删除的部分。

我们可以换个角度思考：将数组分成三部分：左部分 + 删除部分 + 右部分。我们最终的和是 左部分和 + 右部分和。为了让总和最大，我们希望左部分和与右部分和都尽可能大。由于左部分和右部分不重叠，我们可以用动态规划分别计算“以某个位置为结尾的最大子数组和”以及“从某个位置开始的最大子数组和”。

更具体地说，我们定义：

• left_max[i]：表示以 i 位置为结尾的（即子数组的最后一个元素是 arr[i]）最大子数组和。这可以通过经典的 Kadane 算法（动态规划）计算：left_max[i] = max(arr[i], left_max[i-1] + arr[i])。
• right_max[i]：表示从 i 位置开始（即子数组的第一个元素是 arr[i]）的最大子数组和。这可以通过从右向左的动态规划计算：right_max[i] = max(arr[i], right_max[i+1] + arr[i])。

那么，如果我们删除某个子数组 arr[l..r]，剩余元素的和就是 左部分最大和（在 l-1 结尾） + 右部分最大和（从 r+1 开始）。注意，左部分和右部分可以为空（即不选任何元素），此时和为0。

因此，问题转化为：找到所有可能的 i（0 <= i <= n-2），使得 left_max[i] + right_max[i+2] 最大。这里 i 是左部分的结束索引，i+2 是右部分的开始索引，中间 i+1 是删除的部分（可以是一个或多个元素，但在这个公式中我们假设只删除一个元素？不对，我们需要考虑删除任意长度）。

更通用的方法是：我们枚举删除子数组的起始位置 del_start，那么左部分的最大和是 left_max[del_start-1]（如果 del_start > 0），右部分的最大和是 right_max[del_end+1]（如果 del_end < n-1）。但这样枚举起始和结束是 O(n^2)，不可接受。

我们可以简化：实际上，我们只关心删除一个连续子数组后的最大和。这个问题等价于：从原数组中选取两个不相交的连续子数组，使得它们的和最大。而这两个子数组可以相邻，也可以不相邻。

那么，我们可以用动态规划解决：

• 定义 dp[i][0]：表示考虑前 i 个元素，还没有删除任何子数组，能得到的最大和。
• 定义 dp[i][1]：表示考虑前 i 个元素，已经删除了一个子数组（包括可能删除到当前位置），能得到的最大和。

状态转移：

1. 对于 dp[i][0]：即还没有删除任何元素，那么就是经典的最大子数组和：dp[i][0] = max(dp[i-1][0] + arr[i], arr[i])。另外，我们可以选择不选任何左部分，即从0开始，但这里 dp[i][0] 至少包含 arr[i] 自身。
2. 对于 dp[i][1]：有两种情况：
   a. 在之前已经删除过了，现在将 arr[i] 加入右部分：dp[i][1] = dp[i-1][1] + arr[i]。
   b. 刚刚完成删除操作，即删除的子数组在 i 位置结束，那么左部分的最大和是 dp[i-1][0]，右部分从 i 开始只有一个元素 arr[i]。但注意，删除操作完成后，右部分必须从当前位置开始计算最大和吗？实际上，我们可以在删除后，右部分从任意位置开始。但为了动态规划的连续性，我们定义 dp[i][1] 表示“已经删除过，且右部分以 i 结尾的最大和”。这样，我们可以用类似 dp[i][0] 的方式计算右部分的最大和。

但更清晰的另一种动态规划定义是：

• f[i]：表示以 i 结尾的、没有删除过子数组的最大子数组和（即经典的最大子数组和）。
• g[i]：表示以 i 结尾的、已经删除过一个子数组（删除的结束位置不超过 i）的最大子数组和。

状态转移：

1. 对于 f[i]：f[i] = max(f[i-1] + arr[i], arr[i])。
2. 对于 g[i]：有两种选择：
   • 删除操作发生在之前，现在将 arr[i] 加入右部分：g[i] = g[i-1] + arr[i]。
   • 删除操作刚好在 i 位置结束，即我们删除了某个子数组，然后从 i 开始新的子数组（右部分）。但删除操作可能发生在任意位置，我们可以选择在 i 位置之前删除一段，然后从 i 开始新的子数组。为了得到这个最大值，我们需要知道“删除一段子数组”之前左部分的最大和，即 f[j] 对于某个 j < i-1。但这样需要枚举 j，时间复杂度 O(n^2)。

我们可以优化：实际上，g[i] 可以理解为“以 i 结尾，且已经删除了一个子数组（可能为空）的最大和”。那么，删除操作可以有两种情况：

• 情况1：删除的子数组在 i 位置结束，即我们删除了某个子数组，然后从 i 开始新的子数组。那么，左部分的最大和是 f[j]（j < i），右部分从 i 开始，但右部分可以只有 arr[i] 自己，也可以扩展。但为了得到以 i 结尾的右部分最大和，我们需要知道右部分的最大子数组和。实际上，我们可以将“删除”操作视为：我们有一个左部分最大和 f[j]，然后跳过中间一段（删除），然后从 i 开始一个新的子数组。但这样还是需要枚举 j。

一个巧妙的状态定义是：

• dp[i][0]：以 i 结尾的、没有删除过任何元素的最大子数组和（即 f[i]）。
• dp[i][1]：以 i 结尾的、删除过恰好一个元素（这个元素可以是任意一个元素，不一定是连续子数组）的最大子数组和。但问题要求删除一个连续子数组，而不是一个元素。所以这个定义不合适。

我们需要重新思考。

正确解法

实际上，我们可以将问题转化为：求两个不重叠子数组的最大和。这两个子数组分别对应删除操作前后的两部分。我们可以枚举分割点 k，将数组分成 arr[0..k] 和 arr[k+1..n-1] 两部分，然后分别在左右两部分中求最大子数组和。但这样，删除的子数组就是 k+1 到某个位置？不对，左右两部分可以不连续，中间就是删除的部分。所以，我们可以枚举分割点 i，使得左部分在 [0, i] 中取一个最大子数组，右部分在 [i+1, n-1] 中取一个最大子数组。但这样，左右两部分的最大子数组可能相邻，也可能不相邻，中间就是删除的部分。

那么，我们需要计算：

• left_max[i]：表示数组从 0 到 i 范围内，以某个位置结尾的最大子数组和（即子数组必须在 [0, i] 内结束）。但为了得到左部分的最大和，我们实际上需要的是“从 0 到 i 范围内的最大子数组和”，不一定以 i 结尾。我们定义 left_best[i] 为 arr[0..i] 中的最大子数组和。
• 同理，right_best[i] 为 arr[i..n-1] 中的最大子数组和。

那么，对于每个分割点 i（0 <= i < n-1），我们计算 left_best[i] + right_best[i+1] 的最大值。这表示我们在 i 和 i+1 之间分割，左部分在 [0, i] 中取一个最大子数组，右部分在 [i+1, n-1] 中取一个最大子数组，然后加起来。注意，左部分和右部分可以为空（和为0），但题目要求删除后至少剩一个元素，所以如果左右都为空，我们需要特殊处理。

算法步骤：

1. 计算 left_max[i]：以 i 结尾的最大子数组和。left_max[i] = max(arr[i], left_max[i-1] + arr[i])。
2. 计算 left_best[i]：arr[0..i] 中的最大子数组和。left_best[i] = max(left_best[i-1], left_max[i])。
3. 计算 right_max[i]：从 i 开始的最大子数组和（以 i 开头）。right_max[i] = max(arr[i], right_max[i+1] + arr[i])。
4. 计算 right_best[i]：arr[i..n-1] 中的最大子数组和。right_best[i] = max(right_max[i], right_best[i+1])。
5. 枚举分割点 i（0 <= i < n-1），计算 left_best[i] + right_best[i+1] 的最大值。同时，还需要考虑不删除任何元素的情况，即整个数组的最大子数组和（left_best[n-1]）。但注意，不删除任何元素相当于删除一个空子数组，这是允许的，所以最终答案是 max(不删除的情况, 删除的情况)。

边界条件：

• 如果整个数组都是负数，那么最大和就是最大的那个负数。此时，不删除任何元素（即保留那个最大的负数）可能比删除后得到0更好，但题目要求删除后至少剩一个元素，所以必须保留至少一个元素。所以，如果所有 left_best[i] 和 right_best[i] 都是负数，答案就是最大的那个负数。在我们的计算中，left_best[i] 和 right_best[i] 会记录最大的负数，所以 left_best[i] + right_best[i+1] 可能会是两个负数相加，更小。因此，我们需要单独考虑不删除的情况（即整个数组的最大子数组和）。

时间复杂度：O(n)，遍历数组几次。
空间复杂度：O(n)，可以优化到 O(1)，但为了方便理解，我们先保留 O(n)。

示例演算

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

1. 计算 left_max 和 left_best：

   • i=0: left_max[0]=1, left_best[0]=1
   • i=1: left_max[1]=max(-2, 1+(-2))=-1, left_best[1]=max(1, -1)=1
   • i=2: left_max[2]=max(0, -1+0)=0, left_best[2]=max(1, 0)=1
   • i=3: left_max[3]=max(3, 0+3)=3, left_best[3]=max(1, 3)=3

2. 计算 right_max 和 right_best（从右向左）：

   • i=3: right_max[3]=3, right_best[3]=3
   • i=2: right_max[2]=max(0, 0+3)=3, right_best[2]=max(3, 3)=3
   • i=1: right_max[1]=max(-2, -2+3)=1, right_best[1]=max(1, 3)=3
   • i=0: right_max[0]=max(1, 1+1)=2, right_best[0]=max(2, 3)=3

3. 枚举分割点 i：

   • i=0: left_best[0]+right_best[1]=1+3=4
   • i=1: left_best[1]+right_best[2]=1+3=4
   • i=2: left_best[2]+right_best[3]=1+3=4
     最大值为4。

4. 不删除的情况：left_best[3]=3

5. 最终答案：max(3, 4)=4

符合示例。

代码实现（Python）

def maximumSum(arr):
    n = len(arr)
    if n == 1:
        return arr[0]
    
    # left_max[i]: 以 i 结尾的最大子数组和
    left_max = [0] * n
    left_max[0] = arr[0]
    for i in range(1, n):
        left_max[i] = max(arr[i], left_max[i-1] + arr[i])
    
    # left_best[i]: arr[0..i] 中的最大子数组和
    left_best = [0] * n
    left_best[0] = left_max[0]
    for i in range(1, n):
        left_best[i] = max(left_best[i-1], left_max[i])
    
    # right_max[i]: 从 i 开始的最大子数组和（以 i 开头）
    right_max = [0] * n
    right_max[n-1] = arr[n-1]
    for i in range(n-2, -1, -1):
        right_max[i] = max(arr[i], right_max[i+1] + arr[i])
    
    # right_best[i]: arr[i..n-1] 中的最大子数组和
    right_best = [0] * n
    right_best[n-1] = right_max[n-1]
    for i in range(n-2, -1, -1):
        right_best[i] = max(right_max[i], right_best[i+1])
    
    # 不删除任何子数组的情况
    ans = left_best[n-1]
    
    # 枚举分割点
    for i in range(n-1):
        ans = max(ans, left_best[i] + right_best[i+1])
    
    return ans

复杂度分析

• 时间复杂度：O(n)，遍历数组四次。
• 空间复杂度：O(n)，用于存储四个数组。可以优化到 O(1)，但代码会稍复杂。

总结

这个问题通过分解为“左部分最大子数组和 + 右部分最大子数组和”，并利用动态规划预处理出每个位置左右两侧的最大子数组和，从而在线性时间内求解。关键点在于理解删除一个连续子数组等价于将数组分成左右两部分，并分别求最大子数组和。