1. Iterate through the array with a starting index i from 0 to n - k.
2. For each i, consider the subarray from i to i + k - 1.
3. Insert all elements of this subarray into a Set to check for duplicates.
4. If the size of the Set equals k (implying all elements are unique), calculate the sum of the subarray.
5. Track the maximum sum encountered.

python
# Pseudo-code for Brute Force
def maximumSubarraySum(nums, k):
    max_sum = 0
    for i in range(len(nums) - k + 1):
        subarray = nums[i : i + k]
        if len(set(subarray)) == k:  # Check distinct
            current_sum = sum(subarray)
            max_sum = max(max_sum, current_sum)
    return max_sum

Why this fails: The time complexity of this approach is $O(N \cdot K)$. The constraints state that nums.length (N) can be up to $10^5$ and k can also be up to $10^5$. In the worst case, this results in approximately $10^{10}$ operations, which will inevitably trigger a Time Limit Exceeded (TLE) error. We need an $O(N)$ solution.

Core Insight for Maximum Sum of Distinct Subarrays With Length K

The core inefficiency in the brute force method is the repetitive work: re-checking uniqueness and re-calculating the sum for overlapping parts of the subarrays.

The Sliding Window pattern optimizes this by maintaining a "running state" as we traverse the array.

1. State Maintenance: We maintain a running current_sum and a frequency map (or set) of elements currently inside the window [left, right].
2. Handling Duplicates (The Condition): If adding nums[right] creates a duplicate, the window is invalid regardless of its size. We must shrink the window from the left until the duplicate is removed. This ensures the window always contains distinct elements.
3. Handling Size: If the window grows larger than k, we simply shrink from the left to maintain the size constraint.
4. Valid State: Whenever the window size is exactly k and we have ensured distinctness (via step 2), we consider current_sum for the answer.

Visual Description: Imagine a window expanding to the right. As nums[right] enters, we check if it already exists in our window. If it does, the left pointer advances, dropping elements and reducing the sum, until the previous instance of nums[right] is ejected. Only then is the new element valid. Once the window stabilizes with distinct elements, if its width is k, we record the sum.

Execution Flow

Let's trace nums = [1, 5, 4, 2, 9, 9, 9], k = 3.

1. Start: left=0, right=0. Window: [1]. Sum: 1. Size: 1.
2. Expand: right=1. Window: [1, 5]. Sum: 6. Size: 2.
3. Expand: right=2. Window: [1, 5, 4]. Sum: 10. Size: 3. Valid (Size=k). max_sum = 10.
4. Expand: right=3. Window: [1, 5, 4, 2]. Size 4 > k.
   • Shrink left (remove 1). Window: [5, 4, 2]. Sum: 11. Size: 3. Valid. max_sum = 11.
5. Expand: right=4. Window: [5, 4, 2, 9]. Size 4 > k.
   • Shrink left (remove 5). Window: [4, 2, 9]. Sum: 15. Size: 3. Valid. max_sum = 15.
6. Expand: right=5. Element is 9. 9 is already in Set!
   • Shrink left until 9 is removed.
   • Remove 4. Window: [2, 9]. 9 still in set.
   • Remove 2. Window: [9]. 9 still in set.
   • Remove 9. Window: []. 9 gone.
   • Add new 9. Window: [9]. Sum: 9. Size: 1.
7. Expand: right=6. Element is 9. 9 is already in Set!
   • Shrink left (remove 9). Window: [].
   • Add new 9. Window: [9]. Sum: 9. Size: 1.
8. End: Return 15.

Proof of Correctness

The algorithm is correct because it maintains an invariant: the window nums[left...right] always contains distinct elements after the inner while loop executes.

1. We consider every element as the potential end of a subarray (right).
2. For each right, left is adjusted to the minimum index such that nums[left...right] is valid (distinct and length $\le k$).
3. Since we check the sum whenever length equals k, and the window slides continuously covering all valid ranges, we are guaranteed to find the maximum sum.

Reference Implementation

C++ Solution for LeetCode 2461

cpp
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        long long maxSum = 0;
        long long currentSum = 0;
        unordered_set<int> seen;
        int left = 0;
        
        for (int right = 0; right < nums.size(); ++right) {
            // If duplicate exists, shrink window from left until duplicate is removed
            while (seen.count(nums[right])) {
                currentSum -= nums[left];
                seen.erase(nums[left]);
                left++;
            }
            
            // Add current element
            currentSum += nums[right];
            seen.insert(nums[right]);
            
            // If window size exceeds k, shrink from left
            if (right - left + 1 > k) {
                currentSum -= nums[left];
                seen.erase(nums[left]);
                left++;
            }
            
            // If window size is exactly k, update max sum
            if (right - left + 1 == k) {
                maxSum = max(maxSum, currentSum);
            }
        }
        
        return maxSum;
    }
};

Java Solution for LeetCode 2461

java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        long maxSum = 0;
        long currentSum = 0;
        Set<Integer> seen = new HashSet<>();
        int left = 0;
        
        for (int right = 0; right < nums.length; right++) {
            // If duplicate exists, shrink window from left
            while (seen.contains(nums[right])) {
                currentSum -= nums[left];
                seen.remove(nums[left]);
                left++;
            }
            
            // Add current element
            seen.add(nums[right]);
            currentSum += nums[right];
            
            // If window size exceeds k, shrink from left
            if (seen.size() > k) {
                currentSum -= nums[left];
                seen.remove(nums[left]);
                left++;
            }
            
            // If window size is exactly k, update max sum
            if (seen.size() == k) {
                maxSum = Math.max(maxSum, currentSum);
            }
        }
        
        return maxSum;
    }
}

Python Solution for LeetCode 2461

python
class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        max_sum = 0
        current_sum = 0
        seen = set()
        left = 0
        
        for right in range(len(nums)):
            # While duplicate exists, shrink from left
            while nums[right] in seen:
                current_sum -= nums[left]
                seen.remove(nums[left])
                left += 1
            
            # Add current element
            seen.add(nums[right])
            current_sum += nums[right]
            
            # If window size exceeds k, shrink from left
            if len(seen) > k:
                current_sum -= nums[left]
                seen.remove(nums[left])
                left += 1
            
            # If window size is exactly k, update result
            if len(seen) == k:
                max_sum = max(max_sum, current_sum)
                
        return max_sum