Dado un arreglo arr[] de N enteros, la tarea es encontrar el valor máximo posible de ( min * sum ) entre todos los subarreglos posibles que tienen K elementos, donde min denota el entero más pequeño del subarreglo y sum denota la suma de todos los elementos del subarreglo.
Ejemplo :
Entrada : arr[] = {1, 2, 3, 2}, K = 3
Salida : 14
Explicación : Para el subarreglo {2, 3, 2}, la puntuación se da como min(2, 3, 2) * suma (2, 3, 2) = 2 * 7 = 14, que es el máximo posible.Entrada : arr[] = {3, 1, 5, 6, 4, 2}, K = 2
Salida : 55
Enfoque : el problema anterior se puede resolver con la ayuda de la técnica de la ventana deslizante manteniendo una ventana de K elementos durante el recorrido de la array y realizando un seguimiento del elemento mínimo y la suma de todos los elementos en la ventana actual en las variables mínimo y suma respectivamente. El mínimo de todos los subarreglos de tamaño K se puede calcular usando una estructura de datos de conjuntos múltiples similar al algoritmo que se analiza aquí y la suma se puede calcular usando el algoritmo que se analiza aquí . El valor máximo de la suma mínima * sobre todas las ventanas de tamaño K es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to the maximum value of min * sum
// over all possible subarrays of K elements
int maxMinSum(vector<int> arr, int K)
{
// Store the array size
int N = arr.size();
// Multiset data structure to calculate the
// minimum over all K sized subarrays
multiset<int> s;
// Stores the sum of the current window
int sum = 0;
// Loop to calculate the sum and min of the
// 1st window of size K
for (int i = 0; i < K; i++) {
s.insert(arr[i]);
sum += arr[i];
}
// Stores the required answer
int ans = sum * (*s.begin());
// Loop to iterate over the remaining windows
for (int i = K; i < N; i++) {
// Add the current value and remove the
// (i-K)th value from the sum
sum += (arr[i] - arr[i - K]);
// Update the set
s.erase(s.find(arr[i - K]));
s.insert(arr[i]);
// Update answer
ans = max(ans, sum * (*s.begin()));
}
// Return Answer
return ans;
}
// Driver Code
int main()
{
vector<int> arr = { 3, 1, 5, 6, 4, 2 };
int K = 2;
cout << maxMinSum(arr, K);
return 0;
}
Java
// Java implementation for the above approach
import java.util.HashSet;
class GFG {
// Function to the maximum value of min * sum
// over all possible subarrays of K elements
public static int maxMinSum(int[] arr, int K)
{
// Store the array size
int N = arr.length;
// Multiset data structure to calculate the
// minimum over all K sized subarrays
HashSet<Integer> s = new HashSet<Integer>();
// Stores the sum of the current window
int sum = 0;
// Loop to calculate the sum and min of the
// 1st window of size K
for (int i = 0; i < K; i++) {
s.add(arr[i]);
sum += arr[i];
}
// Stores the required answer
int ans = sum * (s.iterator().next());
// Loop to iterate over the remaining windows
for (int i = K; i < N; i++) {
// Add the current value and remove the
// (i-K)th value from the sum
sum += (arr[i] - arr[i - K]);
// Update the set
if (s.contains(arr[i - K]))
s.remove(arr[i - K]);
s.add(arr[i]);
// Update answer
ans = Math.max(ans, sum * (s.iterator().next()));
}
// Return Answer
return ans;
}
// Driver Code
public static void main(String args[]) {
int[] arr = { 3, 1, 5, 6, 4, 2 };
int K = 2;
System.out.println(maxMinSum(arr, K));
}
}
// This code is contributed by saurabh_jaiswal.
Python3
# python implementation for the above approach # Function to the maximum value of min * sum # over all possible subarrays of K elements def maxMinSum(arr, K): # Store the array size N = len(arr) # Multiset data structure to calculate the # minimum over all K sized subarrays s = set() # Stores the sum of the current window sum = 0 # Loop to calculate the sum and min of the # 1st window of size K for i in range(0, K): s.add(arr[i]) sum += arr[i] # Stores the required answer ans = sum * (list(s)[0]) # Loop to iterate over the remaining windows for i in range(K, N): # Add the current value and remove the # (i-K)th value from the sum sum += (arr[i] - arr[i - K]) # Update the set if arr[i-K] in s: s.remove(arr[i-K]) s.add(arr[i]) # Update answer ans = max(ans, sum * (list(s)[0])) # Return Answer return ans # Driver Code if __name__ == "__main__": arr = [3, 1, 5, 6, 4, 2] K = 2 print(maxMinSum(arr, K)) # This code is contributed by rakeshsahni
C#
// C# implementation for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG {
// Function to the maximum value of min * sum
// over all possible subarrays of K elements
public static int maxMinSum(int[] arr, int K)
{
// Store the array size
int N = arr.Length;
// Multiset data structure to calculate the
// minimum over all K sized subarrays
HashSet<int> s = new HashSet<int>();
// Stores the sum of the current window
int sum = 0;
// Loop to calculate the sum and min of the
// 1st window of size K
for (int i = 0; i < K; i++) {
s.Add(arr[i]);
sum += arr[i];
}
// Stores the required answer
int ans = sum * (s.ToList<int>()[0]);
// Loop to iterate over the remaining windows
for (int i = K; i < N; i++) {
// Add the current value and remove the
// (i-K)th value from the sum
sum += (arr[i] - arr[i - K]);
// Update the set
if (s.Contains(arr[i - K]))
s.Remove(arr[i - K]);
s.Add(arr[i]);
// Update answer
ans = Math.Max(ans, sum * (s.ToList<int>()[0]));
}
// Return Answer
return ans;
}
// Driver Code
public static void Main() {
int[] arr = { 3, 1, 5, 6, 4, 2 };
int K = 2;
Console.Write(maxMinSum(arr, K));
}
}
// This code is contributed by saurabh_jaiswal.
Javascript
<script>
// JavaScript Program to implement
// the above approach
function MultiSet() {
let tm = {}; // treemap: works for key >= 0
return { add, erase, first }
function add(x) {
tm[x] ? tm[x]++ : tm[x] = 1;
}
function erase(x) {
delete tm[x];
}
function first() {
let a = Object.keys(tm);
return a[0] - '0';
}
}
// Function to the maximum value of min * sum
// over all possible subarrays of K elements
function maxMinSum(arr, K) {
// Store the array size
let N = arr.length;
// Multiset data structure to calculate the
// minimum over all K sized subarrays
let s = new MultiSet();
// Stores the sum of the current window
let sum = 0;
// Loop to calculate the sum and min of the
// 1st window of size K
for (let i = 0; i < K; i++) {
s.add(arr[i]);
sum += arr[i];
}
// Stores the required answer
let ans = sum * (s.first());
// Loop to iterate over the remaining windows
for (let i = K; i < N; i++) {
// Add the current value and remove the
// (i-K)th value from the sum
sum += (arr[i] - arr[i - K]);
// Update the set
s.erase(arr[i - K]);
s.add(arr[i]);
// Update answer
ans = Math.max(ans, sum * (s.first()));
}
// Return Answer
return ans;
}
// Driver Code
let arr = [3, 1, 5, 6, 4, 2];
let K = 2;
document.write(maxMinSum(arr, K));
// This code is contributed by Potta Lokesh
</script>
55
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA