Maximum Sum of Distinct Subarrays With Length K

class Solution {
public:
    long long findMaxSubarraySum(vector<int>& arr, int k) {
        long long maxSum = 0;
        long long sum = 0;
        int start = 0;
        int finish = 0;

        unordered_map<int, int> lastIndex;

        while (finish < arr.size()) {
            int currentNum = arr[finish];
            int previousIndex =
                (lastIndex.count(currentNum) ? lastIndex[currentNum] : -1);

            while (start <= previousIndex || finish - start + 1 > k) {
                sum -= arr[start];
                start++;
            }
            lastIndex[currentNum] = finish;
            sum += arr[finish];
            if (finish - start + 1 == k) {
                maxSum = max(maxSum, sum);
            }
            finish++;
        }
        return maxSum;
    }
};

The provided C++ code implements a function to find the maximum sum of a subarray of length k, where each element in the subarray is unique. Here's the step-by-step flow:

1. Initialize maxSum to store the maximum sum of any valid subarray and sum to maintain the current subarray sum. Both are set to zero initially.
2. Use two pointers, start and finish, to maintain the current subarray window.
3. A hash map lastIndex keeps track of the most recent index of each element within the window.

During the iteration:

1. Loop through the array using the finish pointer. For each element in arr at index finish:

   • Check if the currentNum has appeared before using lastIndex. If it has, get the index, otherwise set it to -1.

2. Adjust the window if the current number has appeared within the window (start to finish) or if the window size exceeds k:

   • Subtract the element at start from sum and increment the start pointer.

3. Update the lastIndex for the current number to finish and add the number to the sum.

4. Every time the window size hits k, compare the current sum with maxSum and update maxSum if the current is greater.

5. Continue until the finish pointer reaches the end of the array. The function returns maxSum, which holds the maximum sum of all unique k-length subarrays.

The use of a hashmap allows for efficient checking of previous occurrences of numbers within the subarray, effectively maintaining the uniqueness constraint. This approach ensures that the algorithm efficiently computes the maximum possible sum without revisits or redundancy, even for complex input scenarios.

class Solution {

    public long findMaxSumSubarray(int[] array, int maxLen) {
        long maxSum = 0;
        long windowSum = 0;
        int start = 0;
        int finish = 0;

        HashMap<Integer, Integer> lastPosition = new HashMap<>();

        while (finish < array.length) {
            int currentNumber = array[finish];
            int prevIndex = lastPosition.getOrDefault(currentNumber, -1);
            // Adjust the window if number is repeated or window size exceeded
            while (start <= prevIndex || finish - start + 1 > maxLen) {
                windowSum -= array[start];
                start++;
            }
            lastPosition.put(currentNumber, finish);
            windowSum += array[finish];
            if (finish - start + 1 == maxLen) {
                maxSum = Math.max(maxSum, windowSum);
            }
            finish++;
        }
        return maxSum;
    }
}

The provided Java program attempts to find the maximum sum of subarrays that have distinct elements, with each subarray having a length specified by maxLen. The approach uses a sliding window with a hashmap to keep track of the last index where each element was located. This allows the identification and management of subarrays that contain unique values only.

Here's a breakdown of how the solution works:

1. Initialize maxSum to track the highest sum of a subarray, and windowSum to track the sum of the current window or subarray.
2. Start iterating through the array using the finish pointer, treating it as the end of your current subarray.
3. Retrieve the current number from the array and check when it was last encountered using a hashmap.
4. If a number repeats within the subarray, or if the subarray's length exceeds maxLen, adjust the start pointer to maintain the distinctness by moving it past the last occurrence of the repeating number, thereby ensuring all elements in the window are unique.
5. Update the hashmap with the latest occurrence of the current number.
6. If the subarray meets the desired length maxLen, check if its sum (windowSum) is greater than the previously recorded maxSum.
7. Slide the finish pointer to continue examining the next potential subarray until the end of the array is reached.

Upon completion, maxSum holds the value of the maximum sum of a subarray with distinct elements and length maxLen.

Note: Use efficient hashmap operations to quickly look up and update the positions of the elements to ensure the solution remains optimal in terms of runtime, especially for large inputs.

class Solution:
    def findMaxSumOfSubarray(self, numbers: List[int], max_size: int) -> int:
        maximum_sum = 0
        window_sum = 0
        window_start = 0
        window_end = 0
        index_map = {}

        while window_end < len(numbers):
            value_at_end = numbers[window_end]
            previous_index = index_map.get(value_at_end, -1)
            # Adjust the window if the number already exists or the window exceeds the limit
            while window_start <= previous_index or window_end - window_start + 1 > max_size:
                window_sum -= numbers[window_start]
                window_start += 1
            index_map[value_at_end] = window_end
            window_sum += numbers[window_end]
            if window_end - window_start + 1 == max_size:
                maximum_sum = max(maximum_sum, window_sum)
            window_end += 1
        return maximum_sum

For your task of finding the maximum sum of distinct subarrays with a length of k using Python, you can leverage the sliding window technique and hashing. This approach ensures that each element in the subarray is unique and efficiently computes the maximum sum possible for the specified length. Here’s a walkthrough of the implemented solution:

• Initialize Variables: Set maximum_sum and window_sum to 0 for tracking the sums. Use window_start and window_end to define the current window boundaries. Create index_map to store the latest indices of elements to ensure distinct values in the subarray.

• Traverse the Array: Loop over the array using window_end as your iterator. For each iteration:

  • Retrieve the element at the current window_end.
  • Check its last occurrence using index_map. If it has appeared before and is within the current window, or if the window size exceeds k, adjust the window_start to the right until the subarray conditions are met (distinct elements, correct size).

• Update the Window: After adjustments, update index_map for the current element and include the current element's value in window_sum.

• Check for Maximum: If the window size equals k, compare and update the maximum_sum with the current window_sum.

• Return Result: After processing all elements, return maximum_sum which will be the highest sum of any subarray of size k with all distinct elements.

This method is efficient because it minimally adjusts the window to exclude repeated values and its size exceeds k, ensuring that each subarray considered for the maximum sum calculation is valid per the problem constraints. The use of a hashmap (index_map) for tracking the indices of last occurrences of elements speeds up these checks and adjustments.