Maximum Sum of Distinct Subarrays With Length K

Problem Statement

Given an array of integers and an integer K, we need to find the maximum sum of distinct subarrays of length K.

Examples

Example 1:

Input: arr = {4, 3, 2, 6, 7} & K = 3

Output: 15

Explanation: The distinct subarrays of length K are:

• [4, 3, 2] with sum 9
• [3, 2, 6,] with sum 11
• [2, 6, 7] with sum 15

Therefore, the maximum sum of distinct subarrays of length 3 is 15.

Example 2:

Input: arr = {4, 4, 4},  k = 3

Output: 0

Explanation: The subarrays of arr with length 3 are:

• [4, 4, 4] which does not meet the requirement because the element 4 is repeated. We return 0 because no subarrays meet the conditions.

Theory

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

Different Approaches

1 Brute Force Approach

The brute force approach involves generating all distinct subarrays of length K and calculating their sums. Then, we return the maximum sum found among these subarrays.

Algorithm:

1. Initialize a variable maxSum to store the maximum sum found.
2. Iterate through the array from index 0 to n - k, where n is the size of the array.
   1. For each index i, calculate the sum of the subarray from i to i + k - 1.
   2. Update maxSum if the sum of the current subarray is greater than maxSum.
3. Return maxSum.

Code Implementation in C++:

#include <iostream>
#include <vector>

using namespace std;

int maxSumOfDistinctSubarrays(vector<int>& arr, int k) {
    int n = arr.size();
    int maxSum = 0;
    
    // Iterate through the array and consider each subarray of length K
    for (int i = 0; i <= n - k; ++i) {
        int sum = 0;
        
        // Calculate the sum of the current subarray
        for (int j = i; j < i + k; ++j) {
            sum += arr[j];
        }
        
        // Update maxSum if the sum of the current subarray is greater
        maxSum = max(maxSum, sum);
    }
    
    return maxSum;
}

int main() {
    vector<int> arr = {4, 3, 2, 6, 7};
    int k = 3;
    
    cout << "Maximum sum of distinct subarrays with length " << k << " is: " << maxSumOfDistinctSubarrays(arr, k) << endl;
    
    return 0;
}

Complexity Analysis:

Time Complexity:O(n^2)

• The time complexity is O(n^2), where n is the size of the array.

Space Complexity:O(1)

2 Sliding Window Approach (with map)

Code Implementation in C++:

#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

int maxSumOfDistinctSubarrays(vector<int>& arr, int k) {
    int n = arr.size();
    unordered_set<int> window;
    int sum = 0;
    
    // Calculate the sum of the first window
    for (int i = 0; i < k; ++i) {
        if (window.find(arr[i]) == window.end()) {
            window.insert(arr[i]);
            sum += arr[i];
        } else {
            // If the element is not distinct, adjust the window size and sum
            while (window.find(arr[i]) != window.end()) {
                window.erase(arr[i - k]);
                sum -= arr[i - k];
                ++i;
            }
            window.insert(arr[i]);
            sum += arr[i];
        }
    }
    
    int maxSum = sum;
    
    // Slide the window and update the sum
    for (int i = k; i < n; ++i) {
        // Remove the element going out of the window
        sum -= arr[i - k];
        window.erase(arr[i - k]);
        
        // Add the new element
        if (window.find(arr[i]) == window.end()) {
            window.insert(arr[i]);
            sum += arr[i];
        } else {
            // If the new element is not distinct, shrink the window
            while (window.find(arr[i]) != window.end()) {
                sum -= arr[i - k + 1];
                window.erase(arr[i - k + 1]);
                ++i;
            }
            // Add the new element
            window.insert(arr[i]);
            sum += arr[i];
        }
        
        // Update the maximum sum
        maxSum = max(maxSum, sum);
    }
    
    return maxSum;
}

int main() {
    vector<int> arr = {4, 3, 2, 6, 7};
    int k = 3;
    
    cout << "Maximum sum of distinct subarrays with length " << k << " is: " << maxSumOfDistinctSubarrays(arr, k) << endl;
    
    return 0;
}