Maximum sum of subarrays having distinct elements of length K – GeeksforGeeks

Given an array, arr[] and a value k, represent the length of the subarray to be considered. Find the maximum sum that can be obtained from the subarray of length k such that each element of the subarray is unique. If there is no subarray that meets the required condition then return 0.

Examples:

Input: arr[] = {1, 5, 4, 2, 9, 9, 9}, k = 3
Output: 15
Explanation: The possible subarrays of arr 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 element 9 is repeated.
• {9, 9, 9} which does not meet the requirements because element 9 is repeated.

We return 15 because it is the maximum subarray sum of all the subarrays that meet the condition.

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

Approach: The problem can be solved based on the following idea:

The idea is based on two pointer Algorithm, where we will fix the size of the subarray k. Iterate over the array if the size of the map becomes equal to k, Update the maximum sum if required.

Follow the below steps to implement the idea:

• Take a map data structure that will store the elements of the subarray.
• Take two variables currentSum which will store the sum of the current subarray and maxSum which will store the max sum of the subarray present in the given array.  
• Take a variable left that will point to the leftmost index of the element of the subarray considered.
• Iterate the array and perform the following step in each iteration:-
  • Add the current element of the subarray in the map.
  • Decrease the frequency of the left element of the subarray from the map. If the frequency of the leftmost element of the subarray is zero then remove that element from the map.
  • Subtract the leftMost element of the subarray from the currentSum.
  • Add the value of the current element in the currentSum.
  • If the size of the map is equal to k then (which means that all the elements present in the map are unique and hence all the elements of the subarray considered are unique and hence this subarray will be considered) take the max value of currentSum and maxSum. 
  • Increment the left value by 1.

Below is the implementation of the above algorithm:- 

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;

// Function to find maximum sum
int helper(vector<int>& arr, int k)
{

    unordered_map<int, int> mp;
    int currentSum = 0, maxSum = 0;
    int n = arr.size(), left = 0, i = 0;

    // Iterating for length k
    while (i < k && i < n) {

        currentSum += arr[i];
        mp[arr[i]]++;

        i++;
    }

    // If distinct elements present in map
    // equal to k
    if (mp.size() == k) {
        maxSum = currentSum;
    }

    // Iterating over the left array
    for (int i = k; i < n; i++) {

        mp[arr[i]]++;
        mp[arr[left]]--;
        if (mp[arr[left]] == 0) {
            mp.erase(arr[left]);
        }
        currentSum += arr[i];
        currentSum -= arr[left];
        if (mp.size() == k) {
            maxSum = max(maxSum, currentSum);
        }
        ++left;
    }

    // Returning the maximum sum
    return maxSum;
}

// Driver Code
int main()
{
    vector<int> arr = { 1, 5, 4, 2, 9, 9, 9 };
    int k = 3;

    // Function call
    cout << helper(arr, k);
    return 0;
}

Time Complexity: O(n) 
Auxiliary Space: O(k)