1186. Maximum Subarray Sum with One Deletion

Problem

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.

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

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 <= 10⁵
• -10⁴ <= arr[i] <= 10⁴

Test Cases

1
2

class Solution:
    def maximumSum(self, arr: List[int]) -> int:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import pytest

from solution import Solution
from solution2 import Solution as Solution2
from solution3 import Solution as Solution3


@pytest.mark.parametrize('arr, expected', [
    ([1,-2,0,3], 4),
    ([1,-2,-2,3], 3),
    ([-1,-1,-1,-1], -1),

    ([-2,1,-3,4,-1,2,1,-5,4], 10),
    ([1], 1),
    ([5,4,-1,7,8], 24),
    ([-3,2,-2,-1,3,-2,3], 6),
    ([1,2,3,4], 10),

    ([-50], -50),
])
@pytest.mark.parametrize('sol', [Solution(), Solution2(), Solution3()])
def test_solution(sol, arr, expected):
    assert sol.maximumSum(arr) == expected

Thoughts

53. Maximum Subarray 的进阶版，可以删掉至多一个数字。

在 53. Maximum Subarray 中提到「如果一个 subarray 的和大于 0，把它与下一个数相加的结果一定比下一个数自身大。反之，应该从下一个数开启新的 subarray」。整理一下状态值和状态转移。

定义 dl(i) 表示以 i 为右端点的最大 subarray 和（至少包含 arr[i]），可得：

$$\begin{cases} dl(0)=arr[0] \\ dl(i)=\max\{dl(i-1),0\}+arr[i] \end{cases}$$

那么 arr 的最大 subarray 和为：

$$\max_{0\le i<n}{dl(i)}$$

如果删掉一个位置的数字，显然只有删掉负数才会有帮助，删掉之后可以把其前后的 subarries 连起来，才有可能得到更大的和。

仿照 dl 定义 dr(i) 表示以 i 为左端点的最大 subarray 和（至少包含 arr[i]），可得：

$$\begin{cases} dr(n-1)=arr[n-1] \\ dr(i)=\max\{dr(i+1),0\}+arr[i] \end{cases}$$

如果删掉位置 i 的数字，左右两边拼起来的和为 dl(i-1) + dr(i+1)。那么允许删除至多一个数字情况下的最大 subarray 和为：

$$\max\begin{cases} \max_{0\le i<n}{dl(i)} \\ \max_{0<i<n-1}\{dl(i-1)+dr(i+1)\} \end{cases}$$

其中 dl 只需要保留最新的一个值，dr 需要缓存整个数组。时间复杂度 O(n)，空间复杂度 O(n)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def maximumSum(self, arr: list[int]) -> int:
        max2 = lambda a, b: a if a >= b else b
        n = len(arr)
        dr = [0] * n # dr[i] = dr(i+1)
        for i in range(n - 1, 0, -1):
            dr[i-1] = max2(dr[i], 0) + arr[i]

        dl = dp = arr[0]
        for i in range(1, n):
            dp = max2(dp, dl + dr[i])
            dl = max2(dl, 0) + arr[i]
            dp = max2(dp, dl)

        return dp

Less Space

看怎么能不用 O(n) 的辅助空间。

依然用 dl(i) 表示以 i 为右端点的最大 subarray 和（至少包含 arr[i]）。用 dd(i) 表示以 i 为右端点但是删掉至多一个数字之后的最大 subarray 和（虽然以 i 为右端点，但是 arr[i] 可以是被删掉的，此时应至少包含 arr[i-1] 以确保 subarray 不为空）。那么 dd(i) 要么取 dl(i-1)（即删掉 arr[i]），要么取 dd(i-1) + arr[i-1]（保持原本已经可能删掉了的那个数字的删除状态，那就不能再删掉 arr[i]）。所以：

$$\begin{cases} dl(0)=arr[0] \\ dl(i)=\max\{dl(i-1),0\}+arr[i] \end{cases}$$

$$\begin{cases} dd(0)=arr[0] \\ dd(i)=\max\{dl(i-1),dd(i-1)+arr[i]\} \end{cases}$$

这样允许删除至多一个数字情况下的最大 subarray 和为：

$$\max\begin{cases} \max_{0\le i<n}{dl(i)} \\ \max_{0\le i<n}{dd(i)} \end{cases}$$

时间复杂度 O(n)，空间复杂度 O(1)。

1
2
3
4
5
6
7
8
9
10

class Solution:
    def maximumSum(self, arr: list[int]) -> int:
        max2 = lambda a, b: a if a >= b else b
        dl = dd = dp = arr[0]
        for i in range(1, len(arr)):
            dd = max2(dl, dd + arr[i])
            dl = max2(dl, 0) + arr[i]
            dp = max2(dp, max2(dd, dl))

        return dp

开始没直接用这个办法是没想好怎么处理「至多删除一个」数字，因为在 subarray 之外的数字，删不删是没影响的。实际上 dd 表示的就是「至多」删除一次，不是一定要删除一次，只要在递推过程中不会多删除就可以了，至于删了更大还是不删更大，是自适应的。

Another DP

在 53. Maximum Subarray 定义的 第二种 DP 的基础上，重新看如何解本题。沿用那边定义的 ps(i) = Σarr[0...i] 和 low(i)（arr[0...i] 的（小于等于零的）最小前缀和）。

$$\begin{array}{rcl} ps(i) & = &\sum_{j=0}^{i}arr[j] \\ low(i) & = & \min\{0, \min_{0\le j\le i}ps(j)\} \end{array}$$

上边 定义的 dl 可以用 ps 和 low 重写为：$dl(i)=ps(i)-low(i-1)$（不用 low(i) 因为需要保证 subarray 不为空）。

然后把 dd 也改造成在 ps 里减去一个值的形式，如 dd = ps - low2，可得：

$$\begin{array}{rl} low2(i) & =ps(i)-dd(i) \\ & =ps(i)-\max\{dl(i-1),dd(i-1)+arr[i]\} \\ & =\min\begin{cases} ps(i)-dl(i-1) \\ ps(i)-dd(i-1)-arr[i] \end{cases} \\ & =\min\begin{cases} ps(i)-(ps(i-1)-low(i-2)) \\ (ps(i-1)+arr[i])-dd(i-1)-arr[i] \end{cases} \\ & =\min\begin{cases} low(i-2)+arr[i] \\ low2(i-1) \end{cases} \end{array}$$

其中 $low(i-2)+arr[i]$ 对应了删掉 arr[i]（那就至少保留 arr[i-1]）的情况。

可见 low2(i) 的含义是 arr[0...i] 的（小于等于零的）最小前缀和再加上额外被删掉的数字所能得到的最小值，在 ps(i) 中减去此最小值，就是以 i 为右端点但是删掉至多一个数字之后的最大 subarray 和。

最后整个 arr 允许删除至多一个数字情况下的最大 subarray 和为：

$$\begin{array}{rl} & \max\begin{cases} \max_{0\le i<n}{dl(i)} \\ \max_{0\le i<n}{dd(i)} \end{cases} \\ = & \max_{0\le i<n}\{ps(i)-\min\{low(i-1),low2(i)\}\} \end{array}$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def maximumSum2(self, arr: list[int]) -> int:
        min2 = lambda a, b: a if a <= b else b
        max2 = lambda a, b: a if a >= b else b
        ps = largest = arr[0]
        low = 0
        low2 = 0
        for i in range(1, len(arr)):
            low2 = min2(low2, low + arr[i]) # low2(i) = min(low2(i-1), low(i-2) + arr[i])
            low = min2(low, ps) # low(i-1) = min(low(i-2), ps(i-1))
            ps += arr[i] # ps(i) = ps(i-1) + arr[i]
            largest = max2(largest, ps - min2(low, low2)) # dl(i) = ps(i) - low(i-1), dd(i) = ps(i) - low2(i)

        return largest

参考资料

• 本文引用

  • 53. Maximum Subarray

• 反向引用

  • 3410. Maximize Subarray Sum After Removing All Occurrences of One Element

  • 53. Maximum Subarray

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章