Maximum Sum of Distinct Subarrays With Length K

• Initialize maxSum = 0L, currentSum = 0L, and a HashMap<Integer, Integer> freqMap to store element frequencies in the current window.
• Iterate through the nums array with index i from 0 to n-1.
• Add element to window: Add nums[i] to currentSum and increment its count in freqMap.
• Maintain window size: If i >= k, the window is now of size k+1. We must remove the leftmost element, nums[i-k], to shrink it back to size k.
  • Subtract nums[i-k] from currentSum.
  • Decrement the count of nums[i-k] in freqMap.
  • If the count of nums[i-k] becomes 0, remove it from the map to keep the map size accurate for the distinctness check.
• Check for valid subarray: If the window has reached size k (i.e., i >= k-1), check if it meets the distinctness condition.
  • The condition is met if freqMap.size() == k.
  • If it is met, update maxSum = Math.max(maxSum, currentSum).
• After the loop finishes, return maxSum.

This optimized approach avoids the redundant work of the brute-force method by using a sliding window. The window is a conceptual frame of size k that moves across the array one element at a time. We maintain the sum of elements and their frequencies within the current window.

We use a HashMap to store the frequency of each number in the window. A key property we use is that a window of k elements has all distinct numbers if and only if the number of unique keys in our frequency map is exactly k.

The process begins by iterating through the array. For each element, we add it to our window. Once the window reaches size k, we check if it's a valid subarray. Then, for all subsequent elements, we "slide" the window by:

1. Adding the new element from the right to our sum and frequency map.
2. Removing the leftmost element (which is now outside the window) from our sum and frequency map.

After each slide, we check if the map's size is k. If it is, we have a valid subarray, and we update our maximum sum. This way, each element of the input array is processed only a constant number of times, leading to a linear time complexity.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public long maximumSubarraySum(int[] nums, int k) {6        long maxSum = 0;7        long currentSum = 0;8        Map<Integer, Integer> freqMap = new HashMap<>();9        int n = nums.length;10 11        for (int i = 0; i < n; i++) {12            // Add the current element to the window13            currentSum += nums[i];14            freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1);15 16            // If window size is now greater than k, remove the leftmost element17            if (i >= k) {18                int leftElement = nums[i - k];19                currentSum -= leftElement;20                freqMap.put(leftElement, freqMap.get(leftElement) - 1);21                if (freqMap.get(leftElement) == 0) {22                    freqMap.remove(leftElement);23                }24            }25 26            // Check if the current window is valid (size k and all distinct)27            if (i >= k - 1) {28                if (freqMap.size() == k) {29                    maxSum = Math.max(maxSum, currentSum);30                }31            }32        }33        return maxSum;34    }35}

• Initialize a variable maxSum to 0.
• Iterate through the array nums with an index i from 0 to n-k, where n is the length of nums. This loop defines the starting position of each subarray.
• For each i, create a new HashSet to store the elements of the current subarray and a currentSum variable initialized to 0.
• Start an inner loop with index j from i to i + k - 1.
• Inside the inner loop, check if nums[j] can be added to the HashSet. The add method returns false if the element is already present.
• If a duplicate is found, this subarray is invalid. Stop processing it and move to the next starting position i.
• If the element is unique, add it to the set and add its value to currentSum.
• After the inner loop finishes, if no duplicates were found (i.e., the loop completed for all k elements), the subarray is valid. Compare currentSum with maxSum and update maxSum if currentSum is larger.
• After the outer loop completes, return maxSum.

The logic is to check every single subarray of length k. We can use a nested loop structure. The outer loop defines the starting point of the subarray, and the inner loop iterates through the k elements of that subarray.

To check for uniqueness within the k elements, a HashSet is an effective tool. For each subarray, we create a new HashSet. As we iterate through its elements, we add them to the set and also accumulate their sum. If we try to add an element that's already present in the set, we know the subarray has duplicates. In this case, we can immediately discard this subarray and move to the next one.

If the inner loop completes without finding any duplicates, it means all k elements are distinct. We then compare its sum with the maximum sum found so far and update it if necessary. This process is repeated for all n-k+1 possible subarrays.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public long maximumSubarraySum(int[] nums, int k) {6        long maxSum = 0;7        int n = nums.length;8        for (int i = 0; i <= n - k; i++) {9            Set<Integer> distinctElements = new HashSet<>();10            long currentSum = 0;11            boolean hasDuplicates = false;12            // Check the subarray nums[i...i+k-1]13            for (int j = i; j < i + k; j++) {14                if (!distinctElements.add(nums[j])) {15                    hasDuplicates = true;16                    break;17                }18                currentSum += nums[j];19            }20            21            if (!hasDuplicates) {22                maxSum = Math.max(maxSum, currentSum);23            }24        }25        return maxSum;26    }27}