1695. Maximum Erasure Value

1695. Maximum Erasure Value

Question

You are given an array of positive integers nums and want to erase a subarray containing unique elements. The score you get by erasing the subarray is equal to the sum of its elements.

Return the maximum score you can get by erasing exactly one subarray.

An array b is called to be a subarray of a if it forms a contiguous subsequence of a, that is, if it is equal to a[l],a[l+1],...,a[r] for some (l,r).

Solution

滑动窗口+数组统计。

用sum记录窗口内的和,max记录和的最大值。
当新滑入的右侧指针不为0时,从左侧滑出元素并将滑出的元素改为0。
然后将右侧指针指针对应的数组统计改为1并更新当前的和max。

Code

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[] bin = new int[10001];
int left = 0, max = 0, sum = 0;

for(int right = 0; right < nums.length; right++){
sum += nums[right];
while(bin[nums[right]] != 0){
bin[nums[left]] = 0;
sum -= nums[left];
left++;
}
bin[nums[right]] = 1;
max = Math.max(max, sum);
}
return max;
}
}
Author

Xander

Posted on

2022-06-12

Updated on

2022-06-12

Licensed under

Comments