Maximum Sum of Distinct Subarrays With Length K

This approach uses a sliding window of size k to efficiently calculate the sum and check for distinct elements. By sliding the window one element at a time, we can update the sum and element counts in constant time on average, avoiding recalculation.

• 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.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        long maxSum = 0;
        long currentSum = 0;
        Map<Integer, Integer> freqMap = new HashMap<>();
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            // Add the current element to the window
            currentSum += nums[i];
            freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1);

            // If window size is now greater than k, remove the leftmost element
            if (i >= k) {
                int leftElement = nums[i - k];
                currentSum -= leftElement;
                freqMap.put(leftElement, freqMap.get(leftElement) - 1);
                if (freqMap.get(leftElement) == 0) {
                    freqMap.remove(leftElement);
                }
            }

            // Check if the current window is valid (size k and all distinct)
            if (i >= k - 1) {
                if (freqMap.size() == k) {
                    maxSum = Math.max(maxSum, currentSum);
                }
            }
        }
        return maxSum;
    }
}