原文链接: https://leetcode-cn.com/problems/maximum-subarray-sum-with-one-deletion

英文原文

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

中文题目

给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。

换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。

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

请看示例：

示例 1：

输入：arr = [1,-2,0,3]
输出：4
解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。

示例 2：

输入：arr = [1,-2,-2,3]
输出：3
解释：我们直接选出 [3]，这就是最大和。

示例 3：

输入：arr = [-1,-1,-1,-1]
输出：-1
解释：最后得到的子数组不能为空，所以我们不能选择 [-1] 并从中删去 -1 来得到 0。
     我们应该直接选择 [-1]，或者选择 [-1, -1] 再从中删去一个 -1。

 

提示：

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

通过代码

高赞题解

本文思路来源: from link

• 我们定义f ( i ) 和 g ( i )，其中 f( i ) 表示不删除元素的情况下最大子数组和（以arr[i]结尾），g( i ) 代表删除元素的情况下的最大子数组和（以arr[i]结尾）。

  f(i) = Math.max(f(i-1)+arr[i],arr[i]) //要么是当前元素累加之前的和，要么是重新从当前元素开始
  g(i) = Math.max(g(i-1)+arr[i],f(i-1)) 
  //要么是加上当前元素，也就是维持之前删除某个元素的情形，即g[i-1]+arr[i]
  //要么是删除当前这个元素，那么区间[0, i-1]就是不删除元素的情况，即f(i-1)+0（注意是f不是g！！）

• 问题在于初始化：

  f(0)= arr[0] //因为必须要有元素，不能为 0 个元素

  g(0) = 什么呢？

  举个例子，假设我们要计算g(1)：

  g(1) = Math.max(g(0)+arr[1],f(0))//题目提到至少保留一个元素，所以必须要选f(0)，即g(0)要足够小
  // g(0) + arr[1] < arr[0]
  // g(0) < arr[0] - arr[1]
  // 因为 - 10^4 <= arr[i] <= 10^4，所以arr[0]-arr[1] >= -2 * 10^4，即g(0)取-20001即可

• 最后遍历一遍 f 数组和 g 数组找出最大值即可。

• 具体代码如下：

  class Solution {
      public int maximumSum(int[] arr) {
          int len = arr.length;
          int[] f = new int[len];
          int[] g = new int[len];
          int res = arr[0]; 
          f[0] = arr[0];
          g[0] = -200001;
          for(int i=1;i<len;i++){
              f[i] = Math.max(f[i-1]+arr[i],arr[i]);//其实就是f(i-1)是否<0
              g[i] = Math.max(g[i-1]+arr[i],f[i-1]);
              res = Math.max(res,Math.max(f[i],g[i]));
          }
          return res;
      }
  }

最后

感谢@DHF以及@baron 提供了更简洁的代码，感谢@hank 指出传递方程的错误，已更正。

统计信息

通过次数	提交次数	AC比率
7758	19579	39.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言