Dado un arreglo arr[] que consta de N enteros y un entero K , la tarea es encontrar un subarreglo de tamaño K con la suma máxima y el recuento de elementos distintos igual al del arreglo original.
Ejemplos:
Entrada: arr[] = {7, 7, 2, 4, 2, 7, 4, 6, 6, 6}, K = 6
Salida: 31
Explicación: La array dada consta de 4 elementos distintos, es decir, {2, 4 , 6, 7}. El subarreglo de tamaño K que consta de todos estos elementos y la suma máxima es {2, 7, 4, 6, 6, 6} que comienza desde el quinto índice ( indexación basada en 1 ) del arreglo original.
Por lo tanto, la suma del subarreglo = 2 + 7 + 4 + 6 + 6 + 6 = 31.Entrada: arr[] = {1, 2, 5, 5, 19, 2, 1}, K = 4
Salida: 27
Enfoque ingenuo: el enfoque simple es generar todos los subarreglos posibles de tamaño K y verificar si tiene los mismos elementos distintos que el arreglo original. En caso afirmativo, encuentre la suma de este subarreglo. Después de verificar todos los subarreglos, imprima la suma máxima de todos esos subarreglos.
A continuación se muestra la implementación del enfoque anterior:
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 array int 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 code int 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 approach import 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 array def 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 code if __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 approach using 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 array function 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 code var arr = [7, 7, 2, 4, 2, 7, 4, 6, 6, 6]; var K = 6; var N = arr.length; // Stores the count of distinct elements var totalDistinct = distinct(arr, N); document.write(maxSubSum(arr, N, K, totalDistinct)); // This code is contributed by itsok. </script>
31
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es hacer uso de Map . Siga los pasos a continuación para resolver el problema:
- Recorra la array una vez y siga actualizando la frecuencia de los elementos de la array en el Mapa .
- Compruebe si el tamaño del mapa es igual al número total de elementos distintos presentes en la array original o no. Si se encuentra que es cierto, actualice la suma máxima.
- Mientras recorre la array original, si el i -ésimo recorrido cruza K elementos en la array, actualice el mapa eliminando una ocurrencia del (i – K) -ésimo elemento.
- Después de completar los pasos anteriores, imprima la suma máxima obtenida.
A continuación se muestra la implementación del enfoque anterior:
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 array int 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 array void 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 Code int 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 approach import 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 array def 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 array def 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 Code if __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 approach using System; using System.Collections.Generic; class GFG { // Function to count the number of // distinct elements present in the array static 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 array static 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 Code public 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 array function 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 array function 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 Code var arr = [7, 7, 2, 4, 2, 7, 4, 6, 6, 6 ]; var K = 6; // Function Call maxSubarraySum(arr, K); </script>
31
Complejidad temporal: O(N)
Espacio auxiliar: O(N)