[LeetCode] 1186. Maximum Subarray Sum with One Deletion

[grandyang]

Given an array of integers, return the maximum sum for a non-empty subarray (contiguous elements) with at most one element deletion. In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element left and the sum of the remaining elements is maximum possible.

Note that the subarray needs to be non-empty after deleting one element.

Example 1:

Input: arr = [1,-2,0,3]
Output: 4
Explanation: Because we can choose [1, -2, 0, 3] and drop -2, thus the subarray [1, 0, 3] becomes the maximum value.

Example 2:

Input: arr = [1,-2,-2,3]
Output: 3
Explanation: We just choose [3] and it's the maximum sum.

Example 3:

Input: arr = [-1,-1,-1,-1]
Output: -1
Explanation: The final subarray needs to be non-empty. You can't choose [-1] and delete -1 from it, then get an empty subarray to make the sum equals to 0.

Constraints:

• 1 <= arr.length <= 105
• -104 <= arr[i] <= 104

这道题给了一个整型数组，让返回最大的非空子数组之和，应该算是之前那道 Maximum Subarray 的拓展，与之不同的是，这里允许有一次删除某个数字的机会。当然，删除数字操作是可用可不用的，用之的目的也是为了让子数组之和变的更大，所以基本上要删除的数字应该是个负数，毕竟负数才会让和变小。若整个数组都是正数，则完全没有必要删除了。所以这道题还是要像之前那道题的一样，肯定要求出不删除情况下的最大子数组之和，这里还是用卡达内算法 Kadane's Algorithm，可以参见维基百科上的这个帖子。该算法的核心思路是一种动态规划 Dynamic Programming，对于每个位置i，要计算出以该位置为结束位置时的最大子数组的之和，且该位置上的数字一定会被使用。大多情况下，为了节省空间，都用一个变量来代替数组，因为不需要保存之前的状态。而这道题因为允许删除操作的存在，还是要记录每个位置的状态。为啥呢，若将i位置上的数字删除了，实际上原数组就被分为两个部分：[0, i-1] 和 [i+1, n-1]，由于是子数组，则 arr[i-1] 和 arr[i+1] 这两个数字一定要出现在子数组中，那这不就正好是 Kadane 算法定义的 dp 数组么（后半段的定义需要翻转一下），用个 maxEndHere[i] 表示在 [0, i] 范围内以 arr[i] 结尾的最大子数组之和，用 maxStartHere[i] 表示在 [i, n-1] 范围内以 arr[i] 为起始的最大子数组之和，那么移除数字i的最大子数组之和就是 maxEndHere[i-1] + maxStartHere[i+1] 了，分析到这里，代码就不难写了吧，注意别忘了统计不需要删除数字时的最大子数组之和，参见代码如下：

class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int res = arr[0], n = arr.size();
        vector<int> maxEndHere(n), maxStartHere(n);
        maxEndHere[0] = arr[0];
        for (int i = 1; i < n; ++i) {
            maxEndHere[i] = max(arr[i], maxEndHere[i - 1] + arr[i]);
            res = max(res, maxEndHere[i]);
        }
        maxStartHere[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            maxStartHere[i] = max(arr[i], maxStartHere[i + 1] + arr[i]);
        }
        for (int i = 1; i < n - 1; ++i) {
            res = max(res, maxEndHere[i - 1] + maxStartHere[i + 1]);
        }
        return res;
    }
};

Github 同步地址:

#1186

类似题目：

Maximum Subarray

参考资料：

https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/

https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/discuss/377397/Intuitive-Java-Solution-With-Explanation

https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/discuss/377522/C%2B%2B-forward-and-backward-solution-with-explanation-and-picture

LeetCode All in One 题目讲解汇总(持续更新中...)