1695. Maximum Erasure Value
Hash Table, Array, Sliding Window, Review ·Problem Statement
link: LeetCode.cn LeetCode 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:
Input: nums = [4,2,4,5,6]
Output: 17
Input: nums = [5,2,1,2,5,2,1,2,5]
Output: 8
Solution Approach
To find the maximum erasure value by erasing exactly one subarray with unique elements, we can utilize a sliding window approach along with a set to keep track of unique elements in the current window.
Algorithm
-
Sliding Window: Use two pointers l and r to define the boundaries of the sliding window.
-
Update Sum: Move r to expand the window, updating the sum of elements within it.
-
Check for Duplicates: If a duplicate element is found while expanding the window, move l to shrink the window until the duplicate is removed.
-
Maximize Score: Continuously update the maximum sum encountered (res) during the traversal.
Implement
class Solution:
def maximumUniqueSubarray(self, nums: List[int]) -> int:
n = len(nums)
visited = set()
res = 0
l, r = 0, 0
temp_sum = 0
while r < n:
while l < r and nums[r] in visited:
temp_sum -= nums[l]
visited.remove(nums[l])
l += 1
visited.add(nums[r])
temp_sum += nums[r]
res = max(res, temp_sum)
r += 1
return res