Maximum Sum of Distinct Subarrays With Length K

Leetcode Problem:

• Maximum Sum of Distinct Subarrays With Length K

Summary

• Find the maximum subarray sum of all the subarrays of a given array that meet the conditions of having a length of k and all elements distinct.

Approach

• Use a sliding window approach with a hashmap to store the previous index of each number
• Iterate through the array, adding each number to the current sum and removing the number at the leftmost index of the window if it's out of the window
• If the window size is equal to k, update the maximum sum if the current sum is greater.

Complexity

• O(n * k) where n is the length of the array, because in the worst case we might have to check all numbers for each window size k.

Explanation

• The solution uses a sliding window approach with a hashmap to store the previous index of each number
• We initialize the hashmap and the maximum sum
• Then we iterate through the array, adding each number to the current sum and removing the number at the leftmost index of the window if it's out of the window
• If the window size is equal to k, we update the maximum sum if the current sum is greater
• We use a hashmap to store the previous index of each number to efficiently check if a number has been seen before in the current window.

Solution Code:

class Solution {
public:
    long long maximumSubarraySum(vector& nums, int k) {
        long long res = 0;
        unordered_map prev_idx;  // num -> prev index of num
        long long cur_sum = 0;
        
        int l = 0;
        
        for (int r = 0; r < nums.size(); r++) {
            cur_sum += nums[r];
            
            int i = -1;
            if (prev_idx.find(nums[r]) != prev_idx.end()) {
                i = prev_idx[nums[r]];
            }
            
            while (l <= i || r - l + 1 > k) {
                cur_sum -= nums[l];
                l++;
            }
            
            if (r - l + 1 == k) {
                res = max(res, cur_sum);
            }
            
            prev_idx[nums[r]] = r;
        }
        
        return res;
    }
};