Naive 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, calculate its sum and update the maximum sum found so far. If no subarrays meet the criteria, return 0.

Code (Python)

def max_distinct_subarray_sum_naive(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

Time Complexity

O(n*k), where n is the length of the array nums and k is the length of the subarray. This is because we iterate through n-k+1 subarrays and compute the sum of the k elements of each subarray and create a set.

Space Complexity

O(k), because in the worst case the distinct set size can be k. If we do not create a set, the space complexity is O(1).

Optimal Solution: Sliding Window

We can optimize the solution by using a sliding window approach. We maintain a window of size k and a hash map to track the frequency of elements in the window. We slide the window through the array, adding the new element and removing the oldest element in the window. We can check if the number of distinct elements is equal to k by checking if the length of the hash map/ set is equal to k. The sum of the window is tracked along the way.

Code (Python)

def max_distinct_subarray_sum(nums, k):
    max_sum = 0
    current_sum = 0
    freq = {}

    for i in range(k):
        current_sum += nums[i]
        freq[nums[i]] = freq.get(nums[i], 0) + 1

    if len(freq) == k:
        max_sum = current_sum

    for i in range(k, len(nums)):
        current_sum += nums[i] - nums[i - k]

        freq[nums[i]] = freq.get(nums[i], 0) + 1
        freq[nums[i-k]] -= 1
        if freq[nums[i-k]] == 0:
            del freq[nums[i-k]]

        if len(freq) == k:
            max_sum = max(max_sum, current_sum)

    return max_sum

Time Complexity

O(n), where n is the length of the array nums. This is because we iterate through the array once.

Space Complexity

O(k), where k is the size of the sliding window. This is because, in the worst case, the hash map can store k distinct elements.

Edge Cases

• If the input array is empty or k is greater than the length of the array, return 0.
• If k is 1, then the maximum subarray sum is the maximum element in the array.
• If no subarray meets the conditions, return 0.