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 <= 105
1 <= nums[i] <= 104
Solution: Sliding window + Hashset
Maintain a window that has no duplicate elements.
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua class Solution { public: int maximumUniqueSubarray(vector<int>& nums) { const int n = nums.size(); unordered_set<int> t; int ans = 0; for (int l = 0, r = 0, s = 0; r < n; ++r) { while (t.count(nums[r]) && l < r) { s -= nums[l]; t.erase(nums[l++]); } t.insert(nums[r]); ans = max(ans, s += nums[r]); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment