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] <= 104The sliding window technique can be used here to find the maximum sum of a subarray with unique elements. The idea is to maintain a window with unique elements using a HashSet. Start with two pointers, both at the beginning of the array. As you extend the window by moving the right pointer, check if the current element is already in the HashSet:
This Python function uses a sliding window approach with a HashSet to track the current subarray of unique elements. Two pointers are maintained: left and right. The right pointer expands the window, and whenever a duplicate is found, the left pointer moves forward to remove duplicates. This ensures the subarray between left and right remains unique, while continually updating the maximum score.
Java
Time Complexity: O(n), where n is the size of the input array, because each element will be visited at most twice.
Space Complexity: O(min(n, m)), where m is the maximum possible number of unique elements (10,000 in this case).
By using a HashMap, it can be optimized to store the last occurrence index of each element. While iterating, if a duplicate is found, directly jump the left pointer to the element's next position after its last occurrence:
This JavaScript solution uses a HashMap (lastOccurrence) to keep track of the indices at which elements last appeared. As the right pointer moves, if a duplicate is encountered, the left pointer quickly jumps to one position after the last occurrence of the duplicate, maintaining an efficient window of unique elements.
C#
Time Complexity: O(n), each element is processed once and the sum of subarrays is managed efficiently.
Space Complexity: O(n) due to the use of a HashMap for last occurrences.
| Approach | Complexity |
|---|---|
| Sliding Window with HashSet | Time Complexity: O(n), where n is the size of the input array, because each element will be visited at most twice. |
| Optimized Sliding Window using HashMap | Time Complexity: O(n), each element is processed once and the sum of subarrays is managed efficiently. |
Leetcode 1695. Maximum Erasure Value • Fraz • 4,397 views views
Watch 9 more video solutions →Practice Maximum Erasure Value with our built-in code editor and test cases.
Practice on FleetCode