[LeetCode] 1186. Maximum Subarray Sum with One Deletion-526互联

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

删除一次得到子数组最大和。

给你一个整数数组，返回它的某个非空子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。

注意，删除一个元素后，子数组不能为空。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-subarray-sum-with-one-deletion
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是动态规划。这道题算是53题的 followup。注意题目的前半部分，让我们计算某个非空子数组的最大元素总和的时候，这就已经是53题了。但是这道题多了额外的一步，得到某个非空子数组之后，我们还需要删除一个元素，使剩下的元素总和最大。

设 input 数组的长度是 n，那么具体的做法是创建两个长度为 n 的数组，一个 forward 代表从左往右的，以 nums[i] 为结尾的子数组的最大和；一个 backward 代表从右往左的，以 nums[i] 为结尾的子数组的最大和。接着我们按照53题的思路把这两个数组填充好，这样对于任何一个 index i 而言，我就有了两个信息

以 nums[i] 结尾的子数组的最大值
以 nums[i] 开头的子数组的最大值

我们再次扫描一遍，这一次我们扫描的范围是 [1, n - 1]。我们计算一下跳过 nums[i] 的子数组的最大值是多少。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int maximumSum(int[] arr) {
 3         int n = arr.length;
 4         // corner case
 5         if (n == 1) {
 6             return arr[0];
 7         }
 8         
 9         // normal case
10         int[] forward = new int[n];
11         int[] backward = new int[n];
12 
13         // forward[i] 记录以nums[i]为结尾的子数组的最大值是多少，从左往右
14         forward[0] = arr[0];
15         int max = arr[0];
16         for (int i = 1; i < n; i++) {
17             forward[i] = Math.max(forward[i - 1] + arr[i], arr[i]);
18             max = Math.max(max, forward[i]);
19         }
20         
21         // backward[i] 记录以nums[i]为结尾的子数组的最大值是多少，从右往左
22         backward[n - 1] = arr[n - 1];
23         for (int i = n - 2; i >= 0; i--) {
24             backward[i] = Math.max(backward[i + 1] + arr[i], arr[i]);
25         }
26         
27         // 如果去掉nums[i]，剩余部分最大值可以是多少
28         for (int i = 1; i < n - 1; i++) {
29             max = Math.max(max, forward[i - 1] + backward[i + 1]);
30         }
31         return max;
32     }
33 }