LeetCode 1186. Maximum Subarray Sum with One Deletion

Question

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

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.

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

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.

Solution

这个题应该是53. Maximum Subarray的follow up。

• Solution1: 由于题目指我们可以删除一个元素或者不删除，那么我们可以遍历每一个位置然后找寻前面和后面可能存在的最大连续和（解法按照上面的53题即可），就可以找到最大值。伪代码如下:

  for (i = 1; i < n - 1; i++)
  		max = Math.max(max, forward[i - 1] + backward[i + 1]);

• Solution2 : 一开始做的时候自己并没有意识到，并且看见连续的元素，我想到的首先是sliding window，但很快就发现不行。当然，这种求最大最小值的题很多都是用动态规划来求解。设定两个数组，分别是delete以及notDelete。讨论DP的题难免需要讨论四个元素（参考自basketwangCoding），以下展示：

  state:
  delete[n], notDelete[n].代表以i结尾的元素获取的最大值（分别是不删除当前元素、删除当前元素）
  
  init:
  delete[0] = 0, notDelete[n] = arr[0], max= arr[0](因为最少也要包括一个元素);
  
  func:
  delete[i] = Math.max(delete[i - 1] + arr[i], notDelete[i - 1]); // 当前元素删除的情况下最大值可能来自于 上个元素被删除的情况+当前的值 以及 上一个元素没有删除（不加上当前元素）
  notDelete[i] = Math.max(notDelete[i - 1] + arr[i], arr[i]); // 表示到i位置最大的连续和。
  max = Math.max(delete[i], notDelete[i]);
  
  res:
  max

Code

// time: O(n) space:O(n)
    // 其数组表示到当前点 最大的连续和。（所以不删除的数组依然会选择大的连续和情况而并非所有的和）
    public int maximumSum(int[] arr) {
        if (arr == null || arr.length == 0) return 0;
        int n = arr.length;
        int[] delete = new int[n];
        int[] notDelete = new int[n]; 
        delete[0] = 0;
        notDelete[0] = arr[0];
        int max = arr[0]; 
        for (int i = 1; i < n; i++) {
            delete[i] = Math.max(delete[i - 1] + arr[i], notDelete[i - 1]);
            notDelete[i] = Math.max(notDelete[i - 1] + arr[i], arr[i]);
            max = Math.max(Math.max(max, delete[i]), notDelete[i]);
        }
        return max;
    } 

    // 这个用法很妙，参照的是53题一样的思路，只是多加了一个反向的，然后每个点删除。
    // time:O(n) space:O(n)
    public int maximumSum2(int[] arr) {
        if (arr == null || arr.length == 0) return 0;
        int n = arr.length;
        int[] forward = new int[n]; // 以i结束的连续最大和 (0 ~ i)
        int[] backward = new int[n]; // 以i结束的连续最大和(i ~ n)
        int max = arr[0];
        forward[0] = arr[0];
        for (int i = 1; i < n; i++) {
            forward[i] = Math.max(forward[i - 1] + arr[i], arr[i]);
            max = Math.max(max, forward[i]);
        }
        
        backward[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            backward[i] = Math.max(backward[i + 1] + arr[i], arr[i]);
        }
        for (int i = 1; i < n - 1; i++) {
            max = Math.max(max, forward[i - 1] + backward[i + 1]);
        }
        
        return max;
    }

Reference

• https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/discuss/377428/JAVA-O(n)-solution-similar-to-maximum-subarray-sum