LeetCode 题解工作台
删除一次得到子数组最大和
给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。 注意，…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们可以先预处理出数组 以每个元素结尾和开头的最大子数组和，分别存入数组 和 中。 如果我们不删除任何元素，那么最大子数组和就是 或 中的最大值；如果我们删除一个元素，我们可以枚举 中的每个位置 ，计算 $\textit{left}[i-1] + \textit{right}[i+1]$ 的值，取最大值即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。
注意，删除一个元素后，子数组 不能为空。
示例 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
解题思路
方法一：预处理 + 枚举
我们可以先预处理出数组 以每个元素结尾和开头的最大子数组和，分别存入数组 和 中。
如果我们不删除任何元素，那么最大子数组和就是 或 中的最大值；如果我们删除一个元素，我们可以枚举 中的每个位置 ，计算 的值，取最大值即可。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def maximumSum(self, arr: List[int]) -> int:
n = len(arr)
left = [0] * n
right = [0] * n
s = 0
for i, x in enumerate(arr):
s = max(s, 0) + x
left[i] = s
s = 0
for i in range(n - 1, -1, -1):
s = max(s, 0) + arr[i]
right[i] = s
ans = max(left)
for i in range(1, n - 1):
ans = max(ans, left[i - 1] + right[i + 1])
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidates should demonstrate an understanding of dynamic programming and state transitions.
- question_mark
Look for the candidate's ability to handle edge cases such as all negative numbers.
- question_mark
Candidates should be able to optimize the space complexity while maintaining the O(n) time complexity.
常见陷阱
外企场景- error
Candidates may struggle to differentiate between maximum sum without deletion and with deletion.
- error
Failing to account for cases where no deletion is optimal, especially with all negative numbers.
- error
Misunderstanding how to maintain the subarray non-empty while deleting one element.
进阶变体
外企场景- arrow_right_alt
Modify the problem to allow multiple deletions and observe how the approach scales.
- arrow_right_alt
Change the input to include a mix of large positive and negative numbers, testing the ability to skip subarrays efficiently.
- arrow_right_alt
Ask the candidate to implement the problem with constant space complexity using only two variables for tracking the sums.