最近一网友收到一个offer，因为自己在洗澡没有看到，结果过了40分钟hr又把offer给撤回了，关键hr还把他的联系方式给删了，也没办法争取了。
我对这种仅过了40分钟就撤回offer的行为很是不能理解，说明他们也不是真的很缺人，如果真的缺人，也不会在乎那几十分钟，所以不去也挺好。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第1186题：删除一次得到子数组最大和，难度是中等。
给你一个整数数组，返回它的某个非空子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。
示例1：
输入：arr = [1,-2,0,3]
输出：4
解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。
示例2：
输入：arr = [1,-2,0,3]
输出：4
解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。
-
1 <= arr.length <= 10^5
-
-10^4 <= arr[i] <= 10^4
问题分析
这题说的是从原数组中最多删除一个元素，然后求最大连续子数组的和，实际上这是一道动态规划的问题。
我们定义dp[i][0]表示没有删除任何元素且以arr[i]为结尾的最大连续子数组之和。dp[i][1]表示最多删除一个元素且以arr[i]为结尾的最大连续子数组之和，删除前以arr[i]为结尾的也算。最后保存最大值即可。
很明显我们可以得出：
dp[i][0] = Math.max(dp[i - 1][0], 0) + arr[i];
dp[i][1] = Math.max(dp[i - 1][1] + arr[i], dp[i - 1][0]);
dp[i][0]表示没有删除任何元素，以它结尾的最大连续子数组之和是它自己arr[i]加上它前面的连续子数组之和，如果它前面的连续子数组之和为负数，就不要加了 。
dp[i][1]表示最多删除一个元素，也可能是之前就已经删除过，所以我们取dp[i - 1][1] + arr[i]，也可能是之前没有删除过，而是把当前的元素arr[i]给删除了，我们取 dp[i - 1][0]，这两种情况我们取最大值即可。
动态规划有了递推公式就简单了，我们在看下Base Case，第一个元素如果没有删除，则dp[0][0] = arr[0]；如果删除了，则dp[0][1] = 0。
JAVA：
publicintmaximumSum(int[] arr){ int n = arr.length; int[][] dp = newint[n][2]; dp[0][0] = arr[0];// 第一个元素没有删除 dp[0][1] = 0;// 第二个元素被删除 int ans = arr[0];// 保存最大值。 for (int i = 1; i < arr.length; i++) { dp[i][0] = Math.max(dp[i - 1][0], 0) + arr[i]; dp[i][1] = Math.max(dp[i - 1][1] + arr[i], dp[i - 1][0]); ans = Math.max(ans, Math.max(dp[i][0], dp[i][1])); } return ans;}
C++：
public: intmaximumSum(vector<int> &arr){ int n = arr.size(); vector<vector<int>> dp(n, vector<int>(2, 0)); dp[0][0] = arr[0];// 第一个元素没有删除 dp[0][1] = 0;// 第二个元素被删除 int ans = arr[0];// 保存最大值。 for (int i = 1; i < n; i++) { dp[i][0] = max(dp[i - 1][0], 0) + arr[i]; dp[i][1] = max(dp[i - 1][1] + arr[i], dp[i - 1][0]); ans = max(ans, max(dp[i][0], dp[i][1])); } return ans; }
