Dada una array arr[] de N elementos y un entero K . La tarea es encontrar la suma máxima de elementos en un subarreglo de tamaño K , con cada elemento elevado a la potencia de su frecuencia en el subarreglo.
Ejemplos:
Entrada: arr[] = { 2, 1, 2, 3, 3 }, N = 5, K = 3
Salida: 11
Explicación: Subarreglo requerido de tamaño 3 = {2, 3, 3}. La suma es 2 1 + 3 2 = 11, que es la suma máxima posible.Entrada: arr[] = { 4, 9, 6, 5}, N = 4, K = 3
Salida: 20
Explicación: Los dos subarreglos de tamaño 3 son {4, 9, 6} y {9, 6, 5} . El subarreglo {9, 6, 5} tiene la suma = 20.
Enfoque ingenuo: el enfoque más simple es generar todos los subarreglos. Luego, para cada subarreglo, cuente la frecuencia de los elementos y genere la suma. Ahora revisa las sumas para encontrar el máximo.
Complejidad temporal: O(N*K)
Espacio auxiliar: O(N*K)
Enfoque eficiente: un enfoque eficiente es utilizar el concepto de ventana deslizante para evitar generar todos los subarreglos. Luego, para cada ventana, cuente la frecuencia de los elementos en ella y descubra la suma. La suma máxima entre todas las ventanas es la respuesta.
Complejidad temporal: O(N*K)
Espacio auxiliar: O(K)
Enfoque más eficiente: esta idea también se basa en la técnica de la ventana deslizante. Pero en este enfoque se evita contar la frecuencia de cada elemento para cada ventana. Siga los pasos a continuación para implementar la idea:
- Mantenga una ventana de tamaño K que denota el subarreglo.
- Cuando la ventana cambia una posición a la derecha, reste la contribución del elemento inmediatamente a la izquierda de la ventana y el elemento más a la derecha de la ventana.
- Ahora ajuste la frecuencia disminuyendo la frecuencia del elemento inmediatamente a la izquierda de la ventana e incrementando la frecuencia del elemento más a la derecha de la ventana.
- Vuelva a agregar las contribuciones de acuerdo con las nuevas frecuencias de los elementos inmediatamente a la izquierda de la ventana y el elemento más a la derecha de la ventana.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement above approach #include <bits/stdc++.h> using namespace std; #define mod 1000000007 // Function to find the maximum sum // of a K sized subarray long long int maxSum(vector<int>& arr, int N, int K) { long long int ans = 0; // Map to store frequency of elements // of the K sized subarray unordered_map<int, int> freq; for (int j = 0; j < K; j++) { freq[arr[j]]++; } long long int sum = 0; // Sum of the first K sized subarray for (auto m : freq) sum = (sum + ((long long int) (pow(m.first, m.second))) % mod)% mod; // Variable to store ans ans = max(ans, sum); for (int i = 1; i <= N - K; i++) { // Subtract the contribution of // the element immediately left // to the subarray sum -= freq[arr[i - 1]] > 0 ? ((long long int) (pow(arr[i - 1], freq[arr[i - 1]])))% mod : 0; // Update the frequency of // the element immediately left // to the subarray freq[arr[i - 1]]--; // Add back the contribution of // the element immediately left // to the subarray sum += freq[arr[i - 1]] > 0 ? ((long long int) (pow(arr[i - 1], freq[arr[i - 1]])))% mod : 0; // Subtract the contribution of // the rightmost element // of the subarray sum -= freq[arr[i + K - 1]] > 0 ? ((long long int) (pow(arr[i + K - 1], freq[arr[i + K - 1]])))% mod : 0; // Update the frequency of the // rightmost element of the subarray freq[arr[i + K - 1]]++; // Add back the contribution of the // rightmost element of the subarray sum += freq[arr[i + K - 1]] > 0 ? ((long long int) (pow(arr[i + K - 1], freq[arr[i + K - 1]])))% mod : 0; // Update the answer ans = max(ans, sum); } return ans; } // Driver code int main() { // Declare the variable int N = 5, K = 3; vector<int> arr = { 2, 1, 2, 3, 3 }; // Output the variable to STDOUT cout << maxSum(arr, N, K); return 0; }
Java
// Java code to implement above approach import java.util.ArrayList; import java.util.HashMap; class GFG { static int mod = 1000000007; // Function to find the maximum sum // of a K sized subarray static long maxSum(ArrayList<Integer> arr, int N, int K) { long ans = 0; // Map to store frequency of elements // of the K sized subarray HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>(); for (int j = 0; j < K; j++) { if (freq.containsKey(arr.get(j))) { freq.put(arr.get(j), freq.get(arr.get(j)) + 1); } else freq.put(arr.get(j), 1); } long sum = 0; // Sum of the first K sized subarray for (int m : freq.keySet()) { sum = (sum + ((long) (Math.pow(m, freq.get(m)))) % mod) % mod; } // Variable to store ans ans = Math.max(ans, sum); for (int i = 1; i <= N - K; i++) { // Subtract the contribution of // the element immediately left // to the subarray if (freq.containsKey(arr.get(i - 1))) { sum -= freq.get(arr.get(i - 1)) > 0 ? ((long) (Math.pow( arr.get(i - 1), freq.get(arr.get(i - 1))))) % mod : 0; // Update the frequency of // the element immediately left // to the subarray freq.put(arr.get(i - 1), freq.get(arr.get(i - 1)) - 1); // Add back the contribution of // the element immediately left // to the subarray sum += freq.get(arr.get(i - 1)) > 0 ? ((long) (Math.pow( arr.get(i - 1), freq.get(arr.get(i - 1))))) % mod : 0; } // Subtract the contribution of // the rightmost element // of the subarray if (freq.containsKey(arr.get(i + K - 1))) { sum -= freq.get(arr.get(i + K - 1)) > 0 ? ((long) (Math.pow( arr.get(i + K - 1), freq.get(arr.get(i + K - 1))))) % mod : 0; } // Update the frequency of the // rightmost element of the subarray if (freq.containsKey(arr.get(i + K - 1))) freq.put(arr.get(i + K - 1), freq.get(arr.get(i + K - 1)) + 1); else freq.put(arr.get(i + K - 1), 1); // Add back the contribution of the // rightmost element of the subarray sum += freq.get(arr.get(i + K - 1)) > 0 ? ((long) (Math.pow( arr.get(i + K - 1), freq.get(arr.get(i + K - 1))))) % mod : 0; // Update the answer ans = Math.max(ans, sum); } return ans; } // Driver code public static void main(String args[]) { // Declare the variable int N = 5, K = 3; ArrayList<Integer> arr = new ArrayList<Integer>(); arr.add(2); arr.add(1); arr.add(2); arr.add(3); arr.add(3); // Output the variable to STDOUT System.out.println(maxSum(arr, N, K)); } } // This code is contributed by Saurabh Jaiswal
Python3
# Python code for the above approach mod = 1000000007 # Function to find the maximum sum # of a K sized subarray def maxSum(arr, N, K): ans = 0 # Map to store frequency of elements # of the K sized subarray freq = [0] * 100001 for j in range(K): freq[arr[j]] += 1 sum = 0 # Sum of the first K sized subarray for i in range(len(freq)): if (freq[i] != 0): sum += ((i ** freq[i]) % mod) % mod # Variable to store ans ans = max(ans, sum) for i in range(1, N - K + 1): # Subtract the contribution of # the element immediately left # to the subarray sum -= ((arr[i - 1] ** freq[arr[i - 1]]) ) % mod if freq[arr[i - 1]] > 0 else 0 # Update the frequency of # the element immediately left # to the subarray freq[arr[i - 1]] -= 1 # Add back the contribution of # the element immediately left # to the subarray sum += ((arr[i - 1] ** freq[arr[i - 1]]) ) % mod if freq[arr[i - 1]] > 0 else 0 # Subtract the contribution of # the rightmost element # of the subarray sum -= ((arr[i + K - 1] ** freq[arr[i + K - 1]]) ) % mod if freq[arr[i + K - 1]] > 0 else 0 # Update the frequency of the # rightmost element of the subarray freq[arr[i + K - 1]] += 1 # Add back the contribution of the # rightmost element of the subarray sum += ((arr[i + K - 1] ** freq[arr[i + K - 1]]) ) % mod if freq[arr[i + K - 1]] > 0 else 0 # Update the answer print("ans = ",ans, "sum = ",sum) ans = max(ans, sum) return ans # Driver code # Declare the variable N = 5 K = 3 arr = [2, 1, 2, 3, 3] print(maxSum(arr, N, K)) # This code is contributed by gfgking
C#
// C# code to implement above approach using System; using System.Collections.Generic; class GFG { static int mod = 1000000007; // Function to find the maximum sum // of a K sized subarray static long maxSum(List<int> arr, int N, int K) { long ans = 0; // Map to store frequency of elements // of the K sized subarray Dictionary<int, int> freq = new Dictionary<int, int>(); for (int j = 0; j < K; j++) { if (freq.ContainsKey(arr[j])) freq[arr[j]]++; else freq[arr[j]] = 1; } long sum = 0; // Sum of the first K sized subarray foreach(KeyValuePair<int, int> m in freq) { sum = (sum + ((long)(Math.Pow(m.Key, m.Value))) % mod) % mod; } // Variable to store ans ans = Math.Max(ans, sum); for (int i = 1; i <= N - K; i++) { // Subtract the contribution of // the element immediately left // to the subarray if (freq.ContainsKey(arr[i - 1])) { sum -= freq[arr[i - 1]] > 0 ? ((long)(Math.Pow( arr[i - 1], freq[arr[i - 1]]))) % mod : 0; // Update the frequency of // the element immediately left // to the subarray freq[arr[i - 1]]--; // Add back the contribution of // the element immediately left // to the subarray sum += freq[arr[i - 1]] > 0 ? ((long)(Math.Pow( arr[i - 1], freq[arr[i - 1]]))) % mod : 0; } // Subtract the contribution of // the rightmost element // of the subarray if (freq.ContainsKey(arr[i + K - 1])) { sum -= freq[arr[i + K - 1]] > 0 ? ((long)(Math.Pow( arr[i + K - 1], freq[arr[i + K - 1]]))) % mod : 0; } // Update the frequency of the // rightmost element of the subarray if (freq.ContainsKey(arr[i + K - 1])) freq[arr[i + K - 1]]++; else freq[arr[i + K - 1]] = 1; // Add back the contribution of the // rightmost element of the subarray sum += freq[arr[i + K - 1]] > 0 ? ((long)(Math.Pow( arr[i + K - 1], freq[arr[i + K - 1]]))) % mod : 0; // Update the answer ans = Math.Max(ans, sum); } return ans; } // Driver code public static void Main() { // Declare the variable int N = 5, K = 3; List<int> arr = new List<int>() { 2, 1, 2, 3, 3 }; // Output the variable to STDOUT Console.WriteLine(maxSum(arr, N, K)); } } // This code is contributed by ukasp.
Javascript
<script> // JavaScript code for the above approach let mod = 1000000007 // Function to find the maximum sum // of a K sized subarray function maxSum(arr, N, K) { let ans = 0; // Map to store frequency of elements // of the K sized subarray let freq = new Array(100001).fill(0); for (let j = 0; j < K; j++) { freq[arr[j]]++; } let sum = 0; // Sum of the first K sized subarray for (let i = 0; i < freq.length; i++) if (freq[i] != 0) { sum = (sum + ( (Math.pow(i, freq[i]))) % mod) % mod; } // Variable to store ans ans = Math.max(ans, sum); for (let i = 1; i <= N - K; i++) { // Subtract the contribution of // the element immediately left // to the subarray sum -= freq[arr[i - 1]] > 0 ? ( (Math.pow(arr[i - 1], freq[arr[i - 1]]))) % mod : 0; // Update the frequency of // the element immediately left // to the subarray freq[arr[i - 1]]--; // Add back the contribution of // the element immediately left // to the subarray sum += freq[arr[i - 1]] > 0 ? ( (Math.pow(arr[i - 1], freq[arr[i - 1]]))) % mod : 0; // Subtract the contribution of // the rightmost element // of the subarray sum -= freq[arr[i + K - 1]] > 0 ? ( (Math.pow(arr[i + K - 1], freq[arr[i + K - 1]]))) % mod : 0; // Update the frequency of the // rightmost element of the subarray freq[arr[i + K - 1]]++; // Add back the contribution of the // rightmost element of the subarray sum += freq[arr[i + K - 1]] > 0 ? ( (Math.pow(arr[i + K - 1], freq[arr[i + K - 1]]))) % mod : 0; // Update the answer ans = Math.max(ans, sum); } return ans; } // Driver code // Declare the variable let N = 5, K = 3; let arr = [2, 1, 2, 3, 3]; document.write(maxSum(arr, N, K)); // This code is contributed by Potta Lokesh </script>
11
Complejidad temporal: O(N)
Espacio auxiliar: O(K)