GoCalf Calf 的自留地 · 昙花一现

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

Calf

Problem

You are given an integer array nums.

You can do the following operation on the array at most once:

  • Choose any integer x such that nums remains non-empty on removing all occurrences of x.
  • Remove all occurrences of x from the array.

Return the maximum subarray sum across all possible resulting arrays.

A subarray is a contiguous non-empty sequence of elements within an array.

https://leetcode.com/problems/maximize-subarray-sum-after-removing-all-occurrences-of-one-element/

Example 1:

Input: nums = [-3,2,-2,-1,3,-2,3]
Output: 7
Explanation:
We can have the following arrays after at most one operation:

  • The original array is nums = [-3, 2, -2, -1, 3, -2, 3]. The maximum subarray sum is 3 + (-2) + 3 = 4.
  • Deleting all occurences of x = -3 results in nums = [2, -2, -1, 3, -2, 3]. The maximum subarray sum is 3 + (-2) + 3 = 4.
  • Deleting all occurences of x = -2 results in nums = [-3, 2, -1, 3, 3]. The maximum subarray sum is 2 + (-1) + 3 + 3 = 7.
  • Deleting all occurences of x = -1 results in nums = [-3, 2, -2, 3, -2, 3]. The maximum subarray sum is 3 + (-2) + 3 = 4.
  • Deleting all occurences of x = 3 results in nums = [-3, 2, -2, -1, -2]. The maximum subarray sum is 2.

The output is max(4, 4, 7, 4, 2) = 7.

Example 2:

Input: nums = [1,2,3,4]
Output: 10
Explanation:
It is optimal to not perform any operations.

Constraints:

  • 1 <= nums.length <= 10⁵
  • -10⁶ <= nums[i] <= 10⁶

Test Cases

python 
class Solution:
    def maxSubarraySum(self, nums: List[int]) -> int:
solution_test.py下载完整源码
py 
import pytest

from solution import Solution
from solution_slow import Solution as SolutionSlow


@pytest.mark.parametrize('nums, expected', [
    ([-3,2,-2,-1,3,-2,3], 7),
    ([1,2,3,4], 10),

    ([-2,1,-3,4,-1,2,1,-5,4], 10),
    ([1], 1),
    ([5,4,-1,7,8], 24),
    ([-2,-2,-2], -2),
    ([1,-2,0,3], 4),
    ([1,-2,-2,3], 4),
    ([-50], -50),
])
@pytest.mark.parametrize('sol', [Solution(), SolutionSlow()])
def test_solution(sol, nums, expected):
    assert sol.maxSubarraySum(nums) == expected

Thoughts

系列问题：

本题是允许最多删除一个数字的所有 occurrences。

显然只有删掉某个负数，才有可能得到更大的最大子数组。

如果直接 遍历每个负数，计算其所有 occurrences 被删掉之后的最大子数组，时间复杂度是 O(n²)，肯定会超时。这里有大量的重复计算。

沿用前两题中 第二种 DP 的定义，ps(i) = Σnums[0...i] 和 low(i)（nums[0...i] 的（小于等于零的）最小前缀和）。调整 low2(i) 的含义为 arr[0...i] 的（小于等于零的）最小前缀和再加上额外被删掉的数字的所有 occurrences 所能得到的最小值（在 ps(i) 中减去此值，就是以 i 为右端点但是删掉至多一个数字的所有 occurrences 之后的最大 subarray 和）。

在 problem 1186 中只允许删除一个位置的数字，low2 的状态转移为：

low2(i)=min⁡{low(i−2)+arr[i]low2(i−1) low2(i)=\min\begin{cases} low(i-2)+arr[i] \\ low2(i-1) \end{cases}

其中 low(i−2)+arr[i]low(i-2)+arr[i] 对应了删掉 arr[i]（那就至少保留 arr[i-1]）的情况。但在本题，如果删除 arr[i] = v，则还需要删掉 i 左边其他的 v。也就是 low(i - 2) 对应的子数组右边的其他 v 也要加上去。用一个关于 v 的字典来记录这个信息：

low2′(v,i)=min⁡{low2′(v,j)+vlow(i−2)+v low2'(v,i)=\min\begin{cases} low2'(v,j)+v \\ low(i-2)+v \end{cases}

其中 j 是 i 左边的最靠右的值为 v 的位置。这里有个小技巧是并没有刻意记录有几个 v 需要删掉，而是记录上一次遇见 v 的时候，需要从 ps 里减去的值是多少。

这样本题的 low2 的状态转移为：

low2(i)=min⁡{low2′(v,i)low2(i−1) low2(i)=\min\begin{cases} low2'(v,i) \\ low2(i-1) \end{cases}

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

Code

solution.py下载完整源码
py 
from collections import defaultdict


class Solution:
    def maxSubarraySum(self, nums: 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 = nums[0]
        low = 0
        low2v: dict[int, int] = defaultdict(int)
        low2 = 0
        for i in range(1, len(nums)):
            v = nums[i]
            low2v[v] = min2(low2v[v], low) + v # low2'(v,i) = v + min(low2'(v,j), low(i-2))
            low2 = min2(low2, low2v[v]) # low2(i) = min(low2(i-1), low2'(v,i))
            low = min2(low, ps) # low(i-1) = min(low(i-2), ps(i-1))
            ps += nums[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

评论需要 JavaScript。