难度: Medium
给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。
注意，删除一个元素后，子数组 不能为空。
示例 1：
输入：arr = [1,-2,0,3] 输出：4 解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。
示例 2：
输入：arr = [1,-2,-2,3] 输出：3 解释：我们直接选出 [3]，这就是最大和。
示例 3：
输入：arr = [-1,-1,-1,-1]
输出：-1
解释：最后得到的子数组不能为空，所以我们不能选择 [-1] 并从中删去 -1 来得到 0。
我们应该直接选择 [-1]，或者选择 [-1, -1] 再从中删去一个 -1。
提示：
1 <= arr.length <= 105-104 <= arr[i] <= 104运行时间: 71 ms
内存: 24.1 MB
class Solution:
def maximumSum(self, arr: List[int]) -> int:
dp0 = arr[0] # 初始化dp0为首个元素的值
dp1 = 0 # 初始化dp1为0
res = dp0 # 初始化结果为首个元素的值
for i in range(1, len(arr)):
dp1 = max(dp1 + arr[i], dp0) # 更新dp1
dp0 = max(dp0, 0) + arr[i] # 更新dp0
res = max(res, dp0, dp1) # 更新res
return res
本题解采用动态规划的方法来解决问题。定义两个状态：dp0[i] 表示不删除任何元素情况下，以 arr[i] 结尾的最大子数组总和；dp1[i] 表示删除一个元素情况下，以 arr[i] 结尾的最大子数组总和。状态转移方程为 dp1[i] = max(dp1[i-1] + arr[i], dp0[i-1])，它表示要么在前一个删除状态下继续加当前元素，要么从当前位置重新开始计算（删除前一个元素）。同时，dp0[i] = max(dp0[i-1], 0) + arr[i]，表示当前位置的最大子数组和，可以选择加上当前元素或者从当前重新开始。最后结果 res 是在遍历过程中记录的 dp0[i] 和 dp1[i] 的最大值。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def maximumSum(self, arr: List[int]) -> int:
dp0 = arr[0] # dp0[i] 表示不删除任何元素的情况下，以 arr[i] 结尾的最大子数组和
dp1 = 0 # dp1[i] 表示删除一个元素的情况下，以 arr[i] 结尾的最大子数组和
res = dp0 # 初始化结果为第一个元素的值
for i in range(1, len(arr)):
dp1 = max(dp1 + arr[i], dp0) # 更新删除一个元素的状态
dp0 = max(dp0, 0) + arr[i] # 更新不删除任何元素的状态
res = max(res, dp0, dp1) # 更新最终结果
return res
在状态转移方程 dp1[i] = max(dp1[i-1] + arr[i], dp0[i-1]) 中，选项 dp0[i-1] 代表的是在第 i-1 位置结束的最大子数组和且没有删除任何元素的情况。当我们考虑 dp1[i] 的值时，我们的目标是考虑到删除一个元素的情况。如果选择 dp0[i-1] + arr[i]，这将违反只删除一个元素的原则，因为这样会意味着从 i-1 开始没有删除元素并且包括 i 在内，即不删除任何元素。因此，dp0[i-1] 是在不包括 arr[i] 的情况下最大的可能子数组和，这正是我们通过删除 arr[i] 之前的元素（如果需要）到达此状态的含义。
在 dp0 的状态更新公式 dp0[i] = max(dp0[i-1], 0) + arr[i] 中，使用 max(dp0[i-1], 0) 是为了处理子数组的非负起始条件。如果 dp0[i-1] 是负数，继续累加这个负数将会减少总和，不利于获取最大子数组和。因此，如果 dp0[i-1] 为负，重新开始计算子数组和从当前元素 arr[i] 开始，这是因为从当前元素开始可能得到更大的子数组和。
在给定的解法中，dp1 初始化为0实际上是基于考虑到在数组的开始位置，没有实际删除任何元素的情况。这意味着在第一次迭代中，删除操作假设的是可以删除第一个元素，但在实际计算中，由于第一个元素在 dp0 已经被计算，dp1 的初始值为0表示在没有删除任何元素的情况下的初始状态。这是为了确保 dp1 在初始状态能够正确地反映删除一个元素的情况。
在解法中，最终结果 res 是在每一步迭代中同时考虑并更新 dp0[i] 和 dp1[i] 的最大值。dp0[i] 考虑的是不删除任何元素的最大子数组和，而 dp1[i] 考虑的是删除一个元素的情况。通过在每个 i 的位置更新 res 为 dp0[i] 和 dp1[i] 的最大值，我们确保了 res 在只删除一个元素的情况下始终是最优的，因为它实时地跟踪并比较了两种情况的最大可能值。