跳转至

1695. 删除子数组的最大得分#

问题描述#

给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。

返回 只删除一个 子数组可获得的 最大得分 。

如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。

 

示例 1：


输入：nums = [4,2,4,5,6]
输出：17
解释：最优子数组是 [2,4,5,6]

示例 2：


输入：nums = [5,2,1,2,5,2,1,2,5]
输出：8
解释：最优子数组是 [5,2,1] 或 [1,2,5]

 

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104

解题思路#

滑动窗口。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
from itertools import accumulate
from typing import List

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        s = list(accumulate(nums))
        v = {}
        l = 0
        ans = 0
        for i, x in enumerate(nums):
            if v.get(x, -1) >= l:
                ans = max(ans, s[i - 1] - (l and s[l - 1]))
                l = v[x] + 1
            v[x] = i
        ans = max(ans, s[-1] - (l and s[l - 1]))
        return ans
返回顶部

在手机上阅读