1695. Maximum Erasure Value #
Problem #
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).
Example 1:
Input: nums = [4,2,4,5,6]
Output: 17
Explanation: The optimal subarray here is [2,4,5,6].
Example 2:
Input: nums = [5,2,1,2,5,2,1,2,5]
Output: 8
Explanation: The optimal subarray here is [5,2,1] or [1,2,5].
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 104
Problem Summary #
You are given a positive integer array nums. Please delete a subarray containing several distinct elements from it. The score for deleting the subarray is the sum of the elements in the subarray. Return the maximum score obtainable by deleting exactly one subarray. If array b is a contiguous subsequence of array a, that is, if it is equal to a[l],a[l+1],…,a[r], then it is a subarray of a.
Solution Approach #
- After reading the problem, you can immediately identify it as a classic sliding window problem. Use a sliding window to move from left to right, tracking frequencies during the process. If the next element is unique, move the right boundary of the window; otherwise, shrink the window from the left. Update the max value with each move. After scanning through once, the max value is the answer.
Code #
package leetcode
func maximumUniqueSubarray(nums []int) int {
if len(nums) == 0 {
return 0
}
result, left, right, freq := 0, 0, -1, map[int]int{}
for left < len(nums) {
if right+1 < len(nums) && freq[nums[right+1]] == 0 {
freq[nums[right+1]]++
right++
} else {
freq[nums[left]]--
left++
}
sum := 0
for i := left; i <= right; i++ {
sum += nums[i]
}
result = max(result, sum)
}
return result
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}
中文