1. 题目

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

1.1 题意

给定数组，求一段连续子数组，选择是否删去其中一个值，使得和最大，求这个最大和

1.2 分析

时间复杂度可以到O( $n * l o g n$ )

1 <= arr.length <= 10^5
-10^4 <= arr[i] <= 10^4

总所周知，最大子段和是可以使用动态规划求解的：
dp[i] = max(arr[i], dp[i-1]+arr[i]); // dp[i] 表示以第i个数结尾的最大子段和

这题情况类似，但是每个位置有两种情况，删除了数的情况和未删除数当的情况，这两种情况都需要记录。
dp[i][0] = max(arr[i], dp[i-1][0] + arr[i]) // 和上头一样，记录未删除数的情况
dp[i][1] = max(dp[i-1][0], dp[i-1][1] + arr[i]) ; // 删除数的情况，可能由已经删除了数的上一个状态转移，或者删除当前该数

小细节：最后的答案需要搜一遍所有状态的最大值

1.3 我的解法

class Solution {
public:int maximumSum(vector<int>& arr) {// dp[i][0] 未删除元素的以第i个元素结尾的最大子段和// dp[i][1] 已删元素的以第i个元素结尾的最大子段和// dp[i][0] = max(arr[i], dp[i-1][0] + arr[i])// dp[i][1] = max(dp[i-1][0], dp[i-1][1] + arr[i])int n = arr.size();vector<vector<int> > dp(n, vector<int>(2, 0) );// 初始化dp[0][0] = arr[0];dp[0][1] = arr[0];for(int i=1; i<n; i++){dp[i][0] = max(arr[i], dp[i-1][0] + arr[i]);dp[i][1] = max(dp[i-1][0], dp[i-1][1] + arr[i]) ;}int res = arr[0];for(int i=0; i<n; i++){// 搜索答案res = max(res, dp[i][0]);res = max(res, dp[i][1]);}return res;}
};