Maximum Sum of Distinct Subarrays With Length K — LeetCode 2461 Python Solution

The problem

You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions: The length of the subarray is k, and All the elements of the subarray are distinct.

Example

Input

nums = [1,5,4,2,9,9,9], k = 3

Output

15

Explanation

The subarrays of nums with length 3 are:

Python solution

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        cnt = Counter(nums[:k])
        s = sum(nums[:k])
        ans = s if len(cnt) == k else 0
        for i in range(k, len(nums)):
            cnt[nums[i]] += 1
            cnt[nums[i - k]] -= 1
            if cnt[nums[i - k]] == 0:
                cnt.pop(nums[i - k])
            s += nums[i] - nums[i - k]
            if len(cnt) == k:
                ans = max(ans, s)
        return ans

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2461. Maximum Sum of Distinct Subarrays With Length K is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems