Given an array arr[] consisting of N integers and an integer K, the task is to find a subarray of size K with maximum sum and count of distinct elements same as that of the original array.
Examples:
Input: arr[] = {7, 7, 2, 4, 2, 7, 4, 6, 6, 6}, K = 6
Output: 31
Explanation: The given array consists of 4 distinct elements, i.e. {2, 4, 6, 7}. The subarray of size K consisting of all these elements and maximum sum is {2, 7, 4, 6, 6, 6} which starts from 5th index (1-based indexing) of the original array.
Therefore, the sum of the subarray = 2 + 7 + 4 + 6 + 6 + 6 = 31.Input: arr[] = {1, 2, 5, 5, 19, 2, 1}, K = 4
Output: 27
Naive Approach: The simple approach is to generate all possible subarrays of size K and check if it has the same distinct elements as the original array. If yes then find the sum of this subarray. After checking all the subarrays print the maximum sum of all such subarrays.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the number of// distinct elements present in the arrayint distinct(int arr[], int n){ map<int,int> mpp; // Insert all elements into the Set for (int i = 0; i < n; i++) { mpp[arr[i]] = 1; } // Return the size of set return mpp.size();}// Function that finds the maximum// sum of K-length subarray having// same unique elements as arr[]int maxSubSum(int arr[], int n,int k, int totalDistinct){ // Not possible to find a // subarray of size K if (k > n) return 0; int maxm = 0, sum = 0; for (int i = 0; i < n - k + 1; i++) { sum = 0; // Initialize Set set<int> st; // Calculate sum of the distinct elements for (int j = i; j < i + k; j++) { sum += arr[j]; st.insert(arr[j]); } // If the set size is same as the // count of distinct elements if ((int) st.size() == totalDistinct) // Update the maximum value maxm = max(sum, maxm); } return maxm;}// Driver codeint main(){ int arr[] = { 7, 7, 2, 4, 2, 7, 4, 6, 6, 6 }; int K = 6; int N = sizeof(arr)/sizeof(arr[0]); // Stores the count of distinct elements int totalDistinct = distinct(arr, N); cout << (maxSubSum(arr, N, K, totalDistinct)); return 0;}// This code is contributed by mohit kumar 29. |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to count the number of // distinct elements present in the array static int distinct(int arr[], int n) { Set<Integer> set = new HashSet<>(); // Insert all elements into the Set for (int i = 0; i < n; i++) { set.add(arr[i]); } // Return the size of set return set.size(); } // Function that finds the maximum // sum of K-length subarray having // same unique elements as arr[] static int maxSubSum(int arr[], int n, int k, int totalDistinct) { // Not possible to find a // subarray of size K if (k > n) return 0; int max = 0, sum = 0; for (int i = 0; i < n - k + 1; i++) { sum = 0; // Initialize Set Set<Integer> set = new HashSet<>(); // Calculate sum of the distinct elements for (int j = i; j < i + k; j++) { sum += arr[j]; set.add(arr[j]); } // If the set size is same as the // count of distinct elements if (set.size() == totalDistinct) // Update the maximum value max = Math.max(sum, max); } return max; } // Driver Code public static void main(String args[]) { int arr[] = { 7, 7, 2, 4, 2, 7, 4, 6, 6, 6 }; int K = 6; int N = arr.length; // Stores the count of distinct elements int totalDistinct = distinct(arr, N); System.out.println( maxSubSum(arr, N, K, totalDistinct)); }} |
Python3
# Python3 program for the above approach# Function to count the number of# distinct elements present in the arraydef distinct(arr, n): mpp = {} # Insert all elements into the Set for i in range(n): mpp[arr[i]] = 1 # Return the size of set return len(mpp)# Function that finds the maximum# sum of K-length subarray having# same unique elements as arr[]def maxSubSum(arr, n, k, totalDistinct): # Not possible to find a # subarray of size K if (k > n): return 0 maxm = 0 sum = 0 for i in range(n - k + 1): sum = 0 # Initialize Set st = set() # Calculate sum of the distinct elements for j in range(i, i + k, 1): sum += arr[j] st.add(arr[j]) # If the set size is same as the # count of distinct elements if (len(st) == totalDistinct): # Update the maximum value maxm = max(sum, maxm) return maxm# Driver codeif __name__ == '__main__': arr = [ 7, 7, 2, 4, 2, 7, 4, 6, 6, 6 ] K = 6 N = len(arr) # Stores the count of distinct elements totalDistinct = distinct(arr, N) print(maxSubSum(arr, N, K, totalDistinct))# This code is contributed by ipg2016107 |
C#
// C# Program to implement// the above approachusing System;using System.Collections.Generic; class GFG { // Function to count the number of // distinct elements present in the array static int distinct(int[] arr, int n) { HashSet<int> set = new HashSet<int>(); // Insert all elements into the Set for (int i = 0; i < n; i++) { set.Add(arr[i]); } // Return the size of set return set.Count; } // Function that finds the maximum // sum of K-length subarray having // same unique elements as arr[] static int maxSubSum(int[] arr, int n, int k, int totalDistinct) { // Not possible to find a // subarray of size K if (k > n) return 0; int max = 0, sum = 0; for (int i = 0; i < n - k + 1; i++) { sum = 0; // Initialize Set HashSet<int> set = new HashSet<int>(); // Calculate sum of the distinct elements for (int j = i; j < i + k; j++) { sum += arr[j]; set.Add(arr[j]); } // If the set size is same as the // count of distinct elements if (set.Count == totalDistinct) // Update the maximum value max = Math.Max(sum, max); } return max; } // Driver Code public static void Main(String[] args) { int[] arr = { 7, 7, 2, 4, 2, 7, 4, 6, 6, 6 }; int K = 6; int N = arr.Length; // Stores the count of distinct elements int totalDistinct = distinct(arr, N); Console.WriteLine( maxSubSum(arr, N, K, totalDistinct)); }}// This code is contributed by code_hunt. |
Javascript
<script>// Javascript program for the above approach// Function to count the number of// distinct elements present in the arrayfunction distinct(arr, n){ var mpp = new Map(); // Insert all elements into the Set for (var i = 0; i < n; i++) { mpp.set(arr[i], 1); } // Return the size of set return mpp.size;}// Function that finds the maximum// sum of K-length subarray having// same unique elements as arr[]function maxSubSum(arr, n,k, totalDistinct){ // Not possible to find a // subarray of size K if (k > n) return 0; var maxm = 0, sum = 0; for (var i = 0; i < n - k + 1; i++) { sum = 0; // Initialize Set var st = new Set(); // Calculate sum of the distinct elements for (var j = i; j < i + k; j++) { sum += arr[j]; st.add(arr[j]); } // If the set size is same as the // count of distinct elements if ( st.size == totalDistinct) // Update the maximum value maxm = Math.max(sum, maxm); } return maxm;}// Driver codevar arr = [7, 7, 2, 4, 2, 7, 4, 6, 6, 6];var K = 6;var N = arr.length;// Stores the count of distinct elementsvar totalDistinct = distinct(arr, N);document.write(maxSubSum(arr, N, K, totalDistinct));// This code is contributed by itsok.</script> |
Output:
31
Time Complexity: O(N2*log(N))
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the idea is to make use of Map. Follow the steps below to solve the problem:
- Traverse the array once and keep updating the frequency of array elements in the Map.
- Check if the size of the map is equal to the total number of distinct elements present in the original array or not. If found to be true, update the maximum sum.
- While traversing the original array, if the ith traversal crosses K elements in the array, update the Map by deleting an occurrence of (i – K)th element.
- After completing the above steps, print the maximum sum obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;// Function to count the number of// distinct elements present in the arrayint distinct(vector<int>arr, int N){ set<int> st; // Insert array elements into set for(int i = 0; i < N; i++) { st.insert(arr[i]); } // Return the st size return st.size();}// Function to calculate maximum// sum of K-length subarray having// same unique elements as arr[]int maxSubarraySumUtil(vector<int>arr, int N, int K, int totalDistinct){ // Not possible to find an // subarray of length K from // an N-sized array, if K > N if (K > N) return 0; int mx = 0; int sum = 0; map<int, int> mp; // Traverse the array for(int i = 0; i < N; i++) { // Update the mp mp[arr[i]] += 1; sum += arr[i]; // If i >= K, then decrement // arr[i-K] element's one // occurrence if (i >= K) { mp[arr[i - K]] -= 1; sum -= arr[i - K]; // If frequency of any // element is 0 then // remove the element if (mp[arr[i - K]] == 0) mp.erase(arr[i - K]); } // If mp size is same as the // count of distinct elements // of array arr[] then update // maximum sum if (mp.size() == totalDistinct) mx = max(mx, sum); } return mx;}// Function that finds the maximum// sum of K-length subarray having// same number of distinct elements// as the original arrayvoid maxSubarraySum(vector<int>arr, int K){ // Size of array int N = arr.size(); // Stores count of distinct elements int totalDistinct = distinct(arr, N); // Print maximum subarray sum cout<<maxSubarraySumUtil(arr, N, K, totalDistinct);}// Driver Codeint main(){ vector<int>arr { 7, 7, 2, 4, 2, 7, 4, 6, 6, 6 }; int K = 6; // Function Call maxSubarraySum(arr, K);}// This code is contributed by ipg2016107 |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to count the number of // distinct elements present in the array static int distinct(int arr[], int N) { Set<Integer> set = new HashSet<>(); // Insert array elements into Set for (int i = 0; i < N; i++) { set.add(arr[i]); } // Return the Set size return set.size(); } // Function to calculate maximum // sum of K-length subarray having // same unique elements as arr[] static int maxSubarraySumUtil( int arr[], int N, int K, int totalDistinct) { // Not possible to find an // subarray of length K from // an N-sized array, if K > N if (K > N) return 0; int max = 0; int sum = 0; Map<Integer, Integer> map = new HashMap<>(); // Traverse the array for (int i = 0; i < N; i++) { // Update the map map.put(arr[i], map.getOrDefault(arr[i], 0) + 1); sum += arr[i]; // If i >= K, then decrement // arr[i-K] element's one // occurrence if (i >= K) { map.put(arr[i - K], map.get(arr[i - K]) - 1); sum -= arr[i - K]; // If frequency of any // element is 0 then // remove the element if (map.get(arr[i - K]) == 0) map.remove(arr[i - K]); } // If map size is same as the // count of distinct elements // of array arr[] then update // maximum sum if (map.size() == totalDistinct) max = Math.max(max, sum); } return max; } // Function that finds the maximum // sum of K-length subarray having // same number of distinct elements // as the original array static void maxSubarraySum(int arr[], int K) { // Size of array int N = arr.length; // Stores count of distinct elements int totalDistinct = distinct(arr, N); // Print maximum subarray sum System.out.println( maxSubarraySumUtil(arr, N, K, totalDistinct)); } // Driver Code public static void main(String args[]) { int arr[] = { 7, 7, 2, 4, 2, 7, 4, 6, 6, 6 }; int K = 6; // Function Call maxSubarraySum(arr, K); }} |
Python3
# Python 3 program for the above approach# Function to count the number of# distinct elements present in the arraydef distinct(arr, N): st = set() # Insert array elements into set for i in range(N): st.add(arr[i]) # Return the st size return len(st)# Function to calculate maximum# sum of K-length subarray having# same unique elements as arr[]def maxSubarraySumUtil(arr, N, K, totalDistinct): # Not possible to find an # subarray of length K from # an N-sized array, if K > N if (K > N): return 0 mx = 0 sum = 0 mp = {} # Traverse the array for i in range(N): # Update the mp if(arr[i] in mp): mp[arr[i]] += 1 else: mp[arr[i]] = 1 sum += arr[i] # If i >= K, then decrement # arr[i-K] element's one # occurrence if (i >= K): if(arr[i-K] in mp): mp[arr[i - K]] -= 1 sum -= arr[i - K] # If frequency of any # element is 0 then # remove the element if (arr[i-K] in mp and mp[arr[i - K]] == 0): mp.remove(arr[i - K]) # If mp size is same as the # count of distinct elements # of array arr[] then update # maximum sum if (len(mp) == totalDistinct): mx = max(mx, sum) return mx# Function that finds the maximum# sum of K-length subarray having# same number of distinct elements# as the original arraydef maxSubarraySum(arr, K): # Size of array N = len(arr) # Stores count of distinct elements totalDistinct = distinct(arr, N) # Print maximum subarray sum print(maxSubarraySumUtil(arr, N, K, totalDistinct))# Driver Codeif __name__ == '__main__': arr = [7, 7, 2, 4, 2,7, 4, 6, 6, 6] K = 6 # Function Call maxSubarraySum(arr, K) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to count the number of// distinct elements present in the arraystatic int distinct(List<int>arr, int N){ HashSet<int> st = new HashSet<int>(); // Insert array elements into set for(int i = 0; i < N; i++) { st.Add(arr[i]); } // Return the st size return st.Count;}// Function to calculate maximum// sum of K-length subarray having// same unique elements as arr[]static int maxSubarraySumUtil(List<int>arr, int N, int K, int totalDistinct){ // Not possible to find an // subarray of length K from // an N-sized array, if K > N if (K > N) return 0; int mx = 0; int sum = 0; Dictionary<int,int> mp = new Dictionary<int,int>(); // Traverse the array for(int i = 0; i < N; i++) { // Update the mp if(mp.ContainsKey(arr[i])) mp[arr[i]] += 1; else mp[arr[i]] = 1; sum += arr[i]; // If i >= K, then decrement // arr[i-K] element's one // occurrence if (i >= K) { if(mp.ContainsKey(arr[i - K])) mp[arr[i - K]] -= 1; else mp[arr[i - K]] = 1; sum -= arr[i - K]; // If frequency of any // element is 0 then // remove the element if (mp[arr[i - K]] == 0) mp.Remove(arr[i - K]); } // If mp size is same as the // count of distinct elements // of array arr[] then update // maximum sum if (mp.Count == totalDistinct) mx = Math.Max(mx, sum); } return mx;}// Function that finds the maximum// sum of K-length subarray having// same number of distinct elements// as the original arraystatic void maxSubarraySum(List<int>arr, int K){ // Size of array int N = arr.Count; // Stores count of distinct elements int totalDistinct = distinct(arr, N); // Print maximum subarray sum Console.WriteLine(maxSubarraySumUtil(arr, N, K, totalDistinct));}// Driver Codepublic static void Main(){ List<int>arr = new List<int>{ 7, 7, 2, 4, 2, 7, 4, 6, 6, 6 }; int K = 6; // Function Call maxSubarraySum(arr, K);}}// This code is contributed by bgangwar59. |
Javascript
<script>// JavaScript program for the above approach// Function to count the number of// distinct elements present in the arrayfunction distinct(arr, N){ var st = new Set(); // Insert array elements into set for(var i = 0; i < N; i++) { st.add(arr[i]); } // Return the st size return st.size;}// Function to calculate maximum// sum of K-length subarray having// same unique elements as arr[]function maxSubarraySumUtil(arr, N, K, totalDistinct){ // Not possible to find an // subarray of length K from // an N-sized array, if K > N if (K > N) return 0; var mx = 0; var sum = 0; var mp = new Map(); // Traverse the array for(var i=0; i<N; i++) { // Update the mp if(mp.has(arr[i])) mp.set(arr[i], mp.get(arr[i])+1) else mp.set(arr[i], 1) sum += arr[i]; // If i >= K, then decrement // arr[i-K] element's one // occurrence if (i >= K) { if(mp.has(arr[i-K])) mp.set(arr[i-K], mp.get(arr[i-K])-1) sum -= arr[i - K]; // If frequency of any // element is 0 then // remove the element if (mp.has(arr[i - K]) && mp.get(arr[i - K])== 0) mp.delete(arr[i - K]); } // If mp size is same as the // count of distinct elements // of array arr[] then update // maximum sum if (mp.size == totalDistinct) mx = Math.max(mx, sum); } return mx;}// Function that finds the maximum// sum of K-length subarray having// same number of distinct elements// as the original arrayfunction maxSubarraySum(arr, K){ // Size of array var N = arr.length; // Stores count of distinct elements var totalDistinct = distinct(arr, N); // Print maximum subarray sum document.write( maxSubarraySumUtil(arr, N, K, totalDistinct));}// Driver Codevar arr = [7, 7, 2, 4, 2, 7, 4, 6, 6, 6 ];var K = 6;// Function CallmaxSubarraySum(arr, K);</script> |
Output:
31
Time Complexity: O(N*log (N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
