---

1186. 删除一次得到子数组最大和

• 标签：数组、动态规划
• 难度：中等

题目链接

• 1186. 删除一次得到子数组最大和 - 力扣

题目大意

描述：给定一个整数数组 $arr$。你可以从中选出一个子数组（连续的一段），并且可以选择删除其中的至多一个元素（也可以不删）。删除后子数组不能为空。

要求：返回可能的最大子数组和。

说明：

• $1 \le arr.length \le 10^5$。
• $-10^4 \le arr[i] \le 10^4$。

示例：

输入：arr = [1,-2,0,3]
输出：4
解释：选 [1,-2,0,3]，删除 -2，得 [1,0,3] 和 = 4。

解题思路

思路 1：动态规划

这道题是经典「最大子数组和」（Kadane 算法）的变体。区别在于允许删除一个元素。

定义两个状态：

• $dp0$：以当前元素结尾，且没有删除过任何元素的最大子数组和。
• $dp1$：以当前元素结尾，且已经删除了一个元素的最大子数组和。

状态转移：

1. 没删过元素（$dp0$）： 要么延续前面的子数组（$dp0 + arr[i]$），要么从当前位置重新开始（$arr[i]$）。
2. 已删过一个元素（$dp1$）： 要么延续前面已经删过元素的子数组（$dp1 + arr[i]$），要么删除当前元素，即使用前面没删过元素的状态（$dp0$，然后跳过 $arr[i]$）。

用人话讲：遍历到每个数字时，你有两条路——保留它或删除它。用两个变量分别记录「还没用过删除机会」和「已经用过删除机会」的最大和。

步骤拆解：

1. 初始化 $dp0 = arr[0]$，$dp1 = 0$（一开始没有元素可删），答案 $ans = arr[0]$。
2. 从第 2 个元素开始遍历：
   • $dp1 = \max(dp1 + arr[i], dp0)$ —— 已经删了一个元素的延续，或者删掉当前元素。
   • $dp0 = \max(dp0 + arr[i], arr[i])$ —— 没删过的延续，或重新开始。
   • 更新 $ans = \max(ans, dp0, dp1)$。
3. 返回 $ans$。

思路 1：代码

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        
        # dp0: 以当前元素结尾，没删除过元素的最大和
        # dp1: 以当前元素结尾，已删除一个元素的最大和
        dp0 = arr[0]
        dp1 = 0  # 初始无元素可删
        ans = arr[0]
        
        for i in range(1, n):
            # 已经删除过一个元素的：延续之前删过的，或删除当前元素
            dp1 = max(dp1 + arr[i], dp0)
            # 没删除过元素的：延续之前的子数组，或从当前位置重新开始
            dp0 = max(dp0 + arr[i], arr[i])
            
            ans = max(ans, dp0, dp1)
        
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n)$。遍历一次就够了。
• 空间复杂度：$O(1)$。只用了几个变量。