Question

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

English Version

题目描述

给你一个正整数数组 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

解法

方法一：数组或哈希表 + 前缀和

我们用数组或哈希表 $d$ 记录每个数字最后一次出现的位置，用 $s$ 记录前缀和，用 $j$ 记录当前不重复子数组的左端点。

遍历数组，对于每个数字 $v$，如果 $d[v]$ 存在，那么我们更新 $j$ 为 $max(j, d[v])$，这样就保证了当前不重复子数组不包含 $v$，然后更新答案为 $max(ans, s[i] - s[j])$，最后更新 $d[v]$ 为 $i$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $nums$ 的长度。

class Solution:
  def maximumUniqueSubarray(self, nums: List[int]) -> int:
    d = defaultdict(int)
    s = list(accumulate(nums, initial=0))
    ans = j = 0
    for i, v in enumerate(nums, 1):
      j = max(j, d[v])
      ans = max(ans, s[i] - s[j])
      d[v] = i
    return ans

class Solution {
  public int maximumUniqueSubarray(int[] nums) {
    int[] d = new int[10001];
    int n = nums.length;
    int[] s = new int[n + 1];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    int ans = 0, j = 0;
    for (int i = 1; i <= n; ++i) {
      int v = nums[i - 1];
      j = Math.max(j, d[v]);
      ans = Math.max(ans, s[i] - s[j]);
      d[v] = i;
    }
    return ans;
  }
}

class Solution {
public:
  int maximumUniqueSubarray(vector<int>& nums) {
    int d[10001]{};
    int n = nums.size();
    int s[n + 1];
    s[0] = 0;
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    int ans = 0, j = 0;
    for (int i = 1; i <= n; ++i) {
      int v = nums[i - 1];
      j = max(j, d[v]);
      ans = max(ans, s[i] - s[j]);
      d[v] = i;
    }
    return ans;
  }
};

func maximumUniqueSubarray(nums []int) (ans int) {
  d := [10001]int{}
  n := len(nums)
  s := make([]int, n+1)
  for i, v := range nums {
    s[i+1] = s[i] + v
  }
  for i, j := 1, 0; i <= n; i++ {
    v := nums[i-1]
    j = max(j, d[v])
    ans = max(ans, s[i]-s[j])
    d[v] = i
  }
  return
}

function maximumUniqueSubarray(nums: number[]): number {
  const m = Math.max(...nums);
  const n = nums.length;
  const s: number[] = Array.from({ length: n + 1 }, () => 0);
  for (let i = 1; i <= n; ++i) {
    s[i] = s[i - 1] + nums[i - 1];
  }
  const d = Array.from({ length: m + 1 }, () => 0);
  let [ans, j] = [0, 0];
  for (let i = 1; i <= n; ++i) {
    j = Math.max(j, d[nums[i - 1]]);
    ans = Math.max(ans, s[i] - s[j]);
    d[nums[i - 1]] = i;
  }
  return ans;
}