Sponsored
Sponsored
The 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:
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).
1import java.util.HashSet;
2
3public class MaximumErasureValue {
4 public int maximumUniqueSubarray(int[] nums) {
5 HashSet<Integer> uniqueElements = new HashSet<>();
6 int left = 0, currentSum = 0, maxScore = 0;
7 for (int right = 0; right < nums.length; right++) {
8 while (uniqueElements.contains(nums[right])) {
9 uniqueElements.remove(nums[left]);
10 currentSum -= nums[left];
11 left++;
12 }
13 uniqueElements.add(nums[right]);
14 currentSum += nums[right];
15 maxScore = Math.max(maxScore, currentSum);
16 }
17 return maxScore;
18 }
19
20 public static void main(String[] args) {
21 MaximumErasureValue solution = new MaximumErasureValue();
22 int[] nums = {4, 2, 4, 5, 6};
23 System.out.println(solution.maximumUniqueSubarray(nums)); // Output: 17
24 }
25}This Java implementation follows the same sliding window logic with a HashSet to manage unique elements in the current window. The for loop iterates through the array, maintaining the sum of the current window and updating the max score whenever a new unique subarray sum is found.
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:
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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int MaximumUniqueSubarray(int[] nums) {
Dictionary<int, int> lastOccurrence = new Dictionary<int, int>();
int left = 0, currentSum = 0, maxScore = 0;
for (int right = 0; right < nums.Length; right++) {
if (lastOccurrence.ContainsKey(nums[right]) && lastOccurrence[nums[right]] >= left) {
left = lastOccurrence[nums[right]] + 1;
}
int newSum = 0;
for (int i = left; i <= right; i++) {
newSum += nums[i];
}
currentSum = newSum;
maxScore = Math.Max(maxScore, currentSum);
lastOccurrence[nums[right]] = right;
}
return maxScore;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = new int[] { 4, 2, 4, 5, 6 };
Console.WriteLine(sol.MaximumUniqueSubarray(nums)); // Output: 17
}
}This C# solution utilizes a Dictionary to manage the last seen indices of elements. The for loop iterates through the array, adjusting the left pointer and calculating new sums for unique subarrays efficiently, ensuring maximum value is tracked.