题目描述
给你一个正整数数组 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 <= 1051 <= 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | 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;
}
|
方法二：双指针
题目实际上是让我们找出一个最长的子数组，该子数组中所有元素都不相同。我们可以用两个指针 $i$ 和 $j$ 分别指向子数组的左右边界，初始时 $i = 0$, $j = 0$。另外，我们用一个哈希表 $vis$ 记录子数组中的元素。
遍历数组，对于每个数字 $x$，如果 $x$ 在 $vis$ 中，那么我们不断地将 $nums[i]$ 从 $vis$ 中移除，直到 $x$ 不在 $vis$ 中为止。这样我们就找到了一个不包含重复元素的子数组。我们将 $x$ 加入 $vis$，并更新子数组的和 $s$，然后更新答案 $ans = \max(ans, s)$。
遍历结束后，我们就可以得到最大的子数组和。
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $nums$ 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution:
def maximumUniqueSubarray(self, nums: List[int]) -> int:
vis = set()
ans = s = i = 0
for x in nums:
while x in vis:
y = nums[i]
s -= y
vis.remove(y)
i += 1
vis.add(x)
s += x
ans = max(ans, s)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution {
public int maximumUniqueSubarray(int[] nums) {
Set<Integer> vis = new HashSet<>();
int ans = 0, s = 0, i = 0;
for (int x : nums) {
while (vis.contains(x)) {
s -= nums[i];
vis.remove(nums[i++]);
}
vis.add(x);
s += x;
ans = Math.max(ans, s);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution {
public:
int maximumUniqueSubarray(vector<int>& nums) {
unordered_set<int> vis;
int ans = 0, s = 0, i = 0;
for (int x : nums) {
while (vis.contains(x)) {
s -= nums[i];
vis.erase(nums[i++]);
}
vis.insert(x);
s += x;
ans = max(ans, s);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | func maximumUniqueSubarray(nums []int) (ans int) {
vis := map[int]bool{}
var s, i int
for _, x := range nums {
for vis[x] {
s -= nums[i]
vis[nums[i]] = false
i++
}
vis[x] = true
s += x
ans = max(ans, s)
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | function maximumUniqueSubarray(nums: number[]): number {
const vis: Set<number> = new Set();
let [ans, s, i] = [0, 0, 0];
for (const x of nums) {
while (vis.has(x)) {
s -= nums[i];
vis.delete(nums[i++]);
}
vis.add(x);
s += x;
ans = Math.max(ans, s);
}
return ans;
}
|