# 1186. 删除一次得到子数组最大和
### 题目地址(1186. 删除一次得到子数组最大和)
### 题目描述
```
给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。
换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。
注意，删除一个元素后，子数组 不能为空。
请看示例：
示例 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 <= 10^5
-10^4 <= arr[i] <= 10^4
```
### 前置知识
* 数组
* 动态规划
### 公司
* 字节
### 思路
#### 暴力法
符合知觉的做法是求出所有的情况，然后取出最大的。 我们只需要两层循环接口，外循环用于确定我们丢弃的元素，内循环用于计算 subArraySum。
```python
class Solution:
def maximumSum(self, arr: List[int]) -> int:
res = arr[0]
def maxSubSum(arr, skip):
res = maxSub = float("-inf")
for i in range(len(arr)):
if i == skip:
continue
maxSub = max(arr[i], maxSub + arr[i])
res = max(res, maxSub)
return res
# 这里循环到了len(arr)项，表示的是一个都不删除的情况
for i in range(len(arr) + 1):
res = max(res, maxSubSum(arr, i))
return res
```
#### 空间换时间
上面的做法在 LC 上会 TLE， 因此我们需要换一种思路，既然超时了，我们是否可以从空间换时间的角度思考呢？我们可以分别从头尾遍历，建立两个 subArraySub 的数组 l 和 r。 其实这个不难想到，很多题目都用到了这个技巧。
具体做法：
* 一层遍历， 建立 l 数组，l\[i]表示从左边开始的以 arr\[i]结尾的 subArraySum 的最大值
> 这里以 xxx 结尾有两种情况，要么自身就是一个数，要么就是和前面结合构成一个子序列。只要取这两种情况的最大值即可（因为我们的目标是求最大值）
* 一层遍历， 建立 r 数组，r\[i]表示从右边开始的以 arr\[i]结尾的 subArraySum 的最大值
* 一层遍历， 计算 l\[i - 1] + r\[i + 1] 的最大值
> l\[i - 1] + r\[i + 1]的含义就是删除 arr\[i]的子数组最大值
* 上面的这个步骤得到了**删除一个**的子数组最大值。题目要求的是最多删除一个，因此还有一种不删除的情况。不删除的只需要在上面循环**顺便计算**一下即可。
```python
class Solution:
def maximumSum(self, arr: List[int]) -> int:
n = len(arr)
l = [arr[0]] * n
r = [arr[n - 1]] * n
if n == 1:
return arr[0]
res = arr[0]
for i in range(1, n):
l[i] = max(l[i - 1] + arr[i], arr[i])
res = max(res, l[i])
for i in range(n - 2, -1, -1):
r[i] = max(r[i + 1] + arr[i], arr[i])
res = max(res, r[i])
for i in range(1, n - 1):
res = max(res, l[i - 1] + r[i + 1])
return res
```
#### 动态规划
上面的算法虽然时间上有所改善，但是正如标题所说，空间复杂度是 O(n),有没有办法改进呢？答案是使用动态规划。
具体过程：
* 定义 max0，表示以 arr\[i]结尾且一个都不漏的最大子数组和
* 定义 max1，表示以 arr\[i]或者 arr\[i - 1]结尾，可以漏一个的最大子数组和
* 遍历数组，更新 max1 和 max0（注意先更新 max1，因为 max1 用到了上一个 max0）
* 其中 `max1 = max(max1 + arr[i], max0)`, 即删除 arr\[i - 1]或者删除 arr\[i]
* 其中 `max0 = max(max0 + arr[i], arr[i])`， 一个都不删除
```python
#
# @lc app=leetcode.cn id=1186 lang=python3
#
# [1186] 删除一次得到子数组最大和
#
# @lc code=start
class Solution:
def maximumSum(self, arr: List[int]) -> int:
# DP
max0 = arr[0]
max1 = arr[0]
res = arr[0]
n = len(arr)
if n == 1:
return max0
for i in range(1, n):
# 先更新max1，再更新max0，因为max1用到了上一个max0
max1 = max(max1 + arr[i], max0)
max0 = max(max0 + arr[i], arr[i])
res = max(res, max0, max1)
return res
```
**复杂度分析**
* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$
### 关键点解析
* 空间换时间
* 头尾双数组
* 动态规划
### 相关题目
* [42.trapping-rain-water](/leetcode-solution/hard/42.trapping-rain-water.md)
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1186.maximum-subarray-sum-with-one-deletion.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.