题目链接：1186. 删除一次得到子数组最大和（中等）
算法原理：
解法：动态规划
11ms击败40.00%
时间复杂度O(N)
空间复杂度O(N)
①状态表示：
由于最多只能删一次，因此到当前位置i时，要么删了要么没删，所以就多加一维，用0记录已删除的状态，用1记录未删除的状态
dp[i][0]:以i位置为结尾且已删除字符的子数组最大和
dp[i][1]:以i位置为结尾且未删除字符的子数组最大和
②状态转移方程：
遍历到当前位置 i 时，“接着前一个”和“以当前位置重新开始”是两个选择，“已删”和“未删”是两种状态，因此：
（1）当遍历到当前位置i，且已删时，一定会有删除，一定会选择，因此有两个选择：
Ⅰ前一个已删+当前值：dp[i-1][0]+nums[i];
Ⅱ前一个未删+当前值删掉：dp[i-1][1]+0;
取两者最大值：dp[i][0]=Math.max(dp[i-1][0]+nums[i],dp[i-1][1]);
（2）当遍历到当前位置i，且未删时，一定没有删除，未必会选择，因此有两个选择：
Ⅰ前一个选，继续接上：dp[i-1][1]+nums[i];
Ⅱ前一个不选，重新开始：nums[i];
取两者最大值：dp[i][0]=Math.max(dp[i-1][1]+nums[i],nums[i]);
简化为：dp[i][1]=Math.max(dp[i-1][1],0)+nums[i];
③初始化：
dp[0][0]=0：第一个位置已删，为0
dp[0][1]=nums[0]：第一个位置未删，为nums[0]
但是要注意的是dp[0][0]的初始化，因为题目要求删除后数组不为空，因此初始化为0是错的吗？也不是，我们可以调整一下，思考：什么情况下，删掉一个元素就空了？那只能是只有一个元素的时候，因此我们只需在动态规划前判断一下是否只有一个，是的话直接返回即可，如果元素数≥2，那么dp[0][0]=0就是可以的，因此此时还有第二个元素，数组必不为空
④填表顺序：
从左往右
⑤返回值：
每一个以 i 位置结尾的子数组的已删和未删的最大和
空间优化版
6ms击败85.45%
时间复杂度O(N)
空间复杂度O(1)
原理同👉动态规划算法-子数组、子串系列：19.最大子数组和（模板题）
由于每次更新只依赖前一个状态，因此我们可以用两个变量来代替数组的更新
Java代码：
class Solution {
public int maximumSum(int[] nums) {
int n=nums.length;
if(n==1) return nums[0];
//dp[i][0]:以i位置为结尾且已删除字符的子数组最大和
//dp[i][1]:以i位置为结尾且未删除字符的子数组最大和
int[][] dp=new int[n][2];
dp[0][0]=0;
dp[0][1]=nums[0];
int ret=nums[0];
for(int i=1;i<n;i++){
dp[i][0]=Math.max(dp[i-1][0]+nums[i],dp[i-1][1]);
dp[i][1]=Math.max(dp[i-1][1],0)+nums[i];
ret=Math.max(ret,Math.max(dp[i][0],dp[i][1]));
}
return ret;
}
}
class Solution {
//空间优化版
public int maximumSum(int[] nums) {
int n=nums.length;
if(n==1) return nums[0];
int dp0=0,dp1=nums[0];
int ret=nums[0];
for(int i=1;i<n;i++){
dp0=Math.max(dp0+nums[i],dp1);
dp1=Math.max(dp1,0)+nums[i];
ret=Math.max(ret,Math.max(dp0,dp1));
}
return ret;
}
}
