## Max Sum of Distinct Subarrays Length k

###### DESCRIPTION (credit Leetcode.com)

Given an integer array nums and an integer k, write a function to identify the highest possible sum of a subarray within nums, where the subarray meets the following criteria: its length is k, and all of its elements are unique.

###### EXAMPLES

**Example 1**:
Input:

`nums = [3, 2, 2, 3, 4, 6, 7, 7, -1] k = 4`

Output:

`20`

Explanation: The subarrays of nums with length 4 are:

`[3, 2, 2, 3] # elements 3 and 2 are repeated. [2, 2, 3, 4] # element 2 is repeated. [2, 3, 4, 6] # meets the requirements and has a sum of 15. [3, 4, 6, 7] # meets the requirements and has a sum of 20. [4, 6, 7, 7] # element 7 is repeated. [6, 7, 7, -1] # element 7 is repeated.`

We return 20 because it is the maximum subarray sum of all the subarrays that meet the conditions.

Run your code to see results here

## Explanation

This solution uses a fixed-length sliding window to iterate over all subarrays of length k in O(n) time and O(k) space. For each subarray of length k, we check if all elements are distinct. If they are, then we compute the sum of the subarray and compare it to the maximum sum we have seen so far, and return the maximum sum at the end.

We represent the state of the current window using two variables:

- curr_sum: The sum of all elements in the window.
- state: A dictionary mapping each element in the window to the number of times it appears in the window.

We use a for-loop to iterate through each element in nums. For each element, we increment its count in state and add its value to curr_sum. We do this until the window reaches size k:

def maxSum(nums, k):max_sum = 0start = 0state = {}curr_sum = 0for end in range(len(nums)):curr_sum = curr_sum + nums[end]state[nums[end]] = state.get(nums[end], 0) + 1if end - start + 1 == k:if len(state) == k:max_sum = max(max_sum, curr_sum)curr_sum = curr_sum - nums[start]state[nums[start]] = state[nums[start]] - 1if state[nums[start]] == 0:del state[nums[start]]start += 1return max_sum

Expanding window until it reaches size k = 4

Each time the window is of size k, we check if the window contains all distinct elements by comparing the length of state to k (if len(state) == k, then all elements in the window are distinct):

If it is, then we compare curr_sum to max_sum and update max_sum if curr_sum is greater.

We then prepare for the next iteration by contracting the window, which involves decrementing the count of the leftmost element in the window and removing it from state if its count is 0. We also subtract the leftmost element from curr_sum. This allows us to maintain the fixed length of the window.

def maxSum(nums, k):max_sum = 0start = 0state = {}curr_sum = 0for end in range(len(nums)):curr_sum = curr_sum + nums[end]state[nums[end]] = state.get(nums[end], 0) + 1if end - start + 1 == k:if len(state) == k:max_sum = max(max_sum, curr_sum)curr_sum = curr_sum - nums[start]state[nums[start]] = state[nums[start]] - 1if state[nums[start]] == 0:del state[nums[start]]start += 1return max_sum

Expanding and contracting the window until first valid subarray is found

We do this until the window reaches the end of nums and return max_sum at the end.

def maxSum(nums, k):max_sum = 0start = 0state = {}curr_sum = 0for end in range(len(nums)):curr_sum = curr_sum + nums[end]state[nums[end]] = state.get(nums[end], 0) + 1if end - start + 1 == k:if len(state) == k:max_sum = max(max_sum, curr_sum)curr_sum = curr_sum - nums[start]state[nums[start]] = state[nums[start]] - 1if state[nums[start]] == 0:del state[nums[start]]start += 1return max_sum

Expanding and contracting the window until the end of the array.

## Solution

def maxSum(nums, k):max_sum = 0start = 0state = {}curr_sum = 0for end in range(len(nums)):curr_sum = curr_sum + nums[end]state[nums[end]] = state.get(nums[end], 0) + 1if end - start + 1 == k:if len(state) == k:max_sum = max(max_sum, curr_sum)curr_sum = curr_sum - nums[start]state[nums[start]] = state[nums[start]] - 1if state[nums[start]] == 0:del state[nums[start]]start += 1return max_sum

Loading comments...