Dado un entero K y un arreglo A[ ] cuya longitud es múltiplo de K , la tarea es dividir los elementos del arreglo dado en K subconjuntos, cada uno con el mismo número de elementos, de modo que la suma de los elementos máximo y mínimo de cada subconjunto es la suma máxima posible.
Ejemplos:
Entrada: K = 2, A[ ] = {1, 13, 7, 17, 6, 5}
Salida: 37
Explicación:
1er grupo: {1, 5, 17} máximo = 17, mínimo = 1
2do grupo: {6 , 7, 13} máximo = 13, mínimo = 6
Por lo tanto, suma máxima posible = 17 + 1 + 13 + 6 = 37Entrada: K = 2, A[ ] = {10, 10, 10, 10, 11, 11}
Salida: 42
Explicación:
1er grupo: {11, 10, 10} máximo = 11, mínimo = 10
2do grupo: {11 , 10, 10} máximo = 11, mínimo = 10
Por lo tanto, suma máxima posible = 11 + 10 + 11 + 10 = 42
Enfoque ingenuo:
el enfoque más simple para resolver este problema es generar todos los grupos posibles de K subconjuntos de tamaño N/K y para cada grupo, encontrar el máximo y el mínimo en cada subconjunto y calcular su suma. Una vez calculada la suma de todos los grupos, imprima la suma máxima obtenida.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(N)
Enfoque Eficiente:
La idea es optimizar el enfoque anterior usando la Técnica Greedy . Dado que se necesita la suma máxima del elemento máximo y mínimo de cada subconjunto, intente maximizar el elemento máximo y el elemento mínimo. Para el elemento máximo de cada subconjunto, tome los primeros K elementos más grandes de la array dada e inserte cada uno en diferentes subconjuntos. Para el elemento mínimo de cada subconjunto, de la array ordenada, comenzando desde el índice 0 , seleccione cada elemento siguiente en (N / K) – 1 intervalo ya que el tamaño de cada subconjunto es N / K y cada uno ya contiene un elemento máximo.
Siga los pasos a continuación:
- Calcule el número de elementos en cada grupo, es decir (N/K) .
- Ordene todos los elementos de A[ ] en orden no descendente.
- Para la suma de los elementos máximos , agregue todos los elementos más grandes de K de la array ordenada.
- Para la suma de elementos mínimos , a partir del índice 0 , seleccione K elementos cada uno con (N / K) – 1 intervalo y agréguelos.
- Finalmente, calcule la suma de elementos máximos y la suma de elementos mínimos. Imprime la suma de sus respectivas sumas como respuesta final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that prints
// the maximum sum possible
void maximumSum(int arr[],
int n, int k)
{
// Find elements in each group
int elt = n / k;
int sum = 0;
// Sort all elements in
// non-descending order
sort(arr, arr + n);
int count = 0;
int i = n - 1;
// Add K largest elements
while (count < k) {
sum += arr[i];
i--;
count++;
}
count = 0;
i = 0;
// For sum of minimum
// elements from each subset
while (count < k) {
sum += arr[i];
i += elt - 1;
count++;
}
// Printing the maximum sum
cout << sum << "\n";
}
// Driver Code
int main()
{
int Arr[] = { 1, 13, 7, 17, 6, 5 };
int K = 2;
int size = sizeof(Arr) / sizeof(Arr[0]);
maximumSum(Arr, size, K);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.Arrays;
class GFG{
// Function that prints
// the maximum sum possible
static void maximumSum(int arr[],
int n, int k)
{
// Find elements in each group
int elt = n / k;
int sum = 0;
// Sort all elements in
// non-descending order
Arrays.sort(arr);
int count = 0;
int i = n - 1;
// Add K largest elements
while (count < k)
{
sum += arr[i];
i--;
count++;
}
count = 0;
i = 0;
// For sum of minimum
// elements from each subset
while (count < k)
{
sum += arr[i];
i += elt - 1;
count++;
}
// Printing the maximum sum
System.out.println(sum);
}
// Driver code
public static void main (String[] args)
{
int Arr[] = { 1, 13, 7, 17, 6, 5 };
int K = 2;
int size = Arr.length;
maximumSum(Arr, size, K);
}
}
// This code is contributed by Shubham Prakash
Python3
# Python3 program to implement # the above approach # Function that prints # the maximum sum possible def maximumSum(arr, n, k): # Find elements in each group elt = n // k; sum = 0; # Sort all elements in # non-descending order arr.sort(); count = 0; i = n - 1; # Add K largest elements while (count < k): sum += arr[i]; i -= 1; count += 1; count = 0; i = 0; # For sum of minimum # elements from each subset while (count < k): sum += arr[i]; i += elt - 1; count += 1; # Printing the maximum sum print(sum); # Driver code if __name__ == '__main__': Arr = [1, 13, 7, 17, 6, 5]; K = 2; size = len(Arr); maximumSum(Arr, size, K); # This code is contributed by sapnasingh4991
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function that prints
// the maximum sum possible
static void maximumSum(int []arr,
int n, int k)
{
// Find elements in each group
int elt = n / k;
int sum = 0;
// Sort all elements in
// non-descending order
Array.Sort(arr);
int count = 0;
int i = n - 1;
// Add K largest elements
while (count < k)
{
sum += arr[i];
i--;
count++;
}
count = 0;
i = 0;
// For sum of minimum
// elements from each subset
while (count < k)
{
sum += arr[i];
i += elt - 1;
count++;
}
// Printing the maximum sum
Console.WriteLine(sum);
}
// Driver code
public static void Main(String[] args)
{
int []Arr = { 1, 13, 7, 17, 6, 5 };
int K = 2;
int size = Arr.Length;
maximumSum(Arr, size, K);
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// Javascript program implementation
// of the approach
// Function that prints
// the maximum sum possible
function maximumSum(arr, n, k)
{
// Find elements in each group
let elt = (n / k);
let sum = 0;
// Sort all elements in
// non-descending order
arr.sort((a, b) => a - b);
let count = 0;
let i = n - 1;
// Add K largest elements
while (count < k)
{
sum += arr[i];
i--;
count++;
}
count = 0;
i = 0;
// For sum of minimum
// elements from each subset
while (count < k)
{
sum += arr[i];
i += elt - 1;
count++;
}
// Printing the maximum sum
document.write(sum);
}
// Driver Code
let Arr = [ 1, 13, 7, 17, 6, 5 ];
let K = 2;
let size = Arr.length;
maximumSum(Arr, size, K);
</script>
37
Complejidad temporal: O(N*logN)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por nitinkr8991 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA