Maximum Sum of Distinct Subarrays With Length K

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.

Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return 0.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,5,4,2,9,9,9], k = 3
Output: 15
Explanation: The subarrays of nums with length 3 are:
- [1,5,4] which meets the requirements and has a sum of 10.
- [5,4,2] which meets the requirements and has a sum of 11.
- [4,2,9] which meets the requirements and has a sum of 15.
- [2,9,9] which does not meet the requirements because the element 9 is repeated.
- [9,9,9] which does not meet the requirements because the element 9 is repeated.
We return 15 because it is the maximum subarray sum of all the subarrays that meet the conditions

Example 2:

Input: nums = [4,4,4], k = 3
Output: 0
Explanation: The subarrays of nums with length 3 are:
- [4,4,4] which does not meet the requirements because the element 4 is repeated.
We return 0 because no subarrays meet the conditions.

## Maximum Subarray Sum of Distinct Elements

This problem requires us to find the maximum subarray sum of length `k` in an array `nums`, with the constraint that all elements in the subarray must be distinct. If no such subarray exists, we return 0.

### 1. Brute Force Solution

The most straightforward approach is to iterate through all possible subarrays of length `k` and check if each subarray contains distinct elements. If it does, we calculate the sum and update the maximum sum found so far.

```python
def max_subarray_sum_brute_force(nums, k):
    max_sum = 0
    for i in range(len(nums) - k + 1):
        subarray = nums[i:i+k]
        if len(set(subarray)) == k:
            max_sum = max(max_sum, sum(subarray))
    return max_sum

Example:

nums = [1, 5, 4, 2, 9, 9, 9]
k = 3
print(max_subarray_sum_brute_force(nums, k))  # Output: 15

2. Optimal Solution: Sliding Window with Hash Set

To optimize the solution, we can use a sliding window approach combined with a hash set to efficiently check for distinct elements.

1. Initialize a window of size k.
2. Use a hash set to keep track of the elements in the current window.
3. Slide the window through the array. In each step:
   • Add the new element to the window and the hash set.
   • Remove the element that is leaving the window from the hash set.
   • If the size of the hash set is equal to k, then all elements in the window are distinct. Calculate the sum of the window and update the maximum sum if necessary.

def max_subarray_sum_optimal(nums, k):
    max_sum = 0
    window_sum = 0
    window_start = 0
    seen = set()

    for window_end in range(len(nums)):
        # Expand the window
        num = nums[window_end]

        # If the current number is already in the window, shrink the window from the left
        while num in seen:
            seen.remove(nums[window_start])
            window_sum -= nums[window_start]
            window_start += 1

        seen.add(num)
        window_sum += num

        # If the window size is k, check the sum and shrink the window
        if window_end - window_start + 1 == k:
            max_sum = max(max_sum, window_sum)
            

    return max_sum

Example:

nums = [1, 5, 4, 2, 9, 9, 9]
k = 3
print(max_subarray_sum_optimal(nums, k))  # Output: 15

3. Big(O) Run-time Analysis

• Brute Force: O(nk) because we iterate through 'n-k+1' subarrays and summing each one takes O(k). The distinct check is technically O(k), but it is dominated by the summation so we can exclude it. Thus, the total is O(nk).
• Optimal: O(n). Although we have a while loop inside the for loop, each element is added and removed from the seen set at most once. Therefore, the amortized time complexity is O(n).

4. Big(O) Space Usage Analysis

• Brute Force: O(1). We only use a constant amount of extra space.
• Optimal: O(k). The hash set seen stores at most k elements, resulting in O(k) space complexity.

5. Edge Cases and Handling

• Empty Array: If the input array is empty, the function should return 0.
• k = 0: If k is 0, the function should return 0.
• k > len(nums): If k is greater than the length of the input array, no valid subarray exists, and the function should return 0.
• All elements are the same: If all the elements are same, the algorithm should return 0 as there is no distinct subarray.

def max_subarray_sum_optimal_edge_cases(nums, k):
    if not nums or k == 0 or k > len(nums):
        return 0

    max_sum = 0
    window_sum = 0
    window_start = 0
    seen = set()

    for window_end in range(len(nums)):
        # Expand the window
        num = nums[window_end]

        # If the current number is already in the window, shrink the window from the left
        while num in seen:
            seen.remove(nums[window_start])
            window_sum -= nums[window_start]
            window_start += 1

        seen.add(num)
        window_sum += num

        # If the window size is k, check the sum and shrink the window
        if window_end - window_start + 1 == k:
            if len(seen) == k:
                max_sum = max(max_sum, window_sum)
            seen.remove(nums[window_start]) #remove left element from seen
            window_sum -= nums[window_start] #subtract left element value from window_sum
            window_start += 1 #slide window ahead

    return max_sum