Input: s ="adaa", chars ="d", vals =[-1000]Output: 2Explanation: The value of the characters "a" and "d"is1 and -1000 respectively.The substring with the maximum cost is"aa" and its cost is1+1=2.It can be proven that 2is the maximum cost.
Input: s ="abc", chars ="abc", vals =[-1,-1,-1]Output: 0Explanation: The value of the characters "a","b" and "c"is-1,-1, and -1 respectively.The substring with the maximum cost is the empty substring "" and its cost is0.It can be proven that 0is the maximum cost.
To maximize the sum of a subarray with unique elements, we need to find continuous windows without repetitions, and among all such windows, choose the one with the highest sum.
classSolution {
public:int maxSum(vector<int>& nums) {
unordered_set<int> seen;
int sum =0, ans = INT_MIN, start =0;
for (int end =0; end < nums.size(); ++end) {
while (seen.count(nums[end])) {
seen.erase(nums[start]);
sum -= nums[start++];
}
if (nums[end] >0) {
seen.insert(nums[end]);
sum += nums[end];
}
ans = max(ans, sum);
ans = max(ans, nums[end]);
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution {
intmaxSum(int[] nums) {
Set<Integer> seen =new HashSet<>();
int sum = 0;
int max = Integer.MIN_VALUE;
for (int num : nums) {
if (num > 0 && seen.add(num)) {
sum += num;
}
max = Math.max(max, num);
}
return (sum > 0) ? sum : max;
}
}
1
2
3
4
5
6
7
8
9
10
11
classSolution:
defmaxSum(self, nums: list[int]) -> int:
seen: set[int] = set()
sum_: int =0 max_: int = float('-inf')
for num in nums:
if num >0and num notin seen:
seen.add(num)
sum_ += num
max_ = max(max_, num)
return sum_ if sum_ >0else max_
Instead of using a sliding window, we can simply keep all unique positive numbers and sum them. This works because we can delete any negative or duplicate numbers, and the sum of all unique positive numbers will be the answer.
classSolution {
public:int maxSum(vector<int>& nums) {
int n = nums.size();
if (n ==1) return nums[0];
int max_one =*max_element(nums.begin(), nums.end());
if (max_one <0) return max_one;
unordered_set<int> seen;
int ans =0;
for (int num : nums) {
if (num >0&&!seen.count(num)) {
seen.insert(num);
ans += num;
}
}
return ans;
}
};
classSolution {
publicintmaxSum(int[] nums) {
int n = nums.length;
if (n == 1) {
return nums[0];
}
int max_one = Arrays.stream(nums).max().getAsInt();
if (max_one < 0) {
return max_one;
}
Set<Integer> seen =new HashSet<>();
int maxSum = 0;
for (int num : nums) {
if (num > 0 &&!seen.contains(num)) {
seen.add(num);
maxSum += num;
}
}
return maxSum;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution:
defmaxSum(self, nums: list[int]) -> int:
n: int = len(nums)
if n ==1:
return nums[0]
max_one: int = max(nums)
if max_one <0:
return max_one
seen: set[int] = set()
ans: int =0for num in nums:
if num >0and num notin seen:
seen.add(num)
ans += num
return ans