Dada una array arr[] que consta de N enteros positivos y un entero K . En una operación, seleccione un elemento de array, agréguelo a la suma y luego disminúyalo en 1 . La tarea es imprimir la suma máxima que se puede obtener realizando la operación K veces.
Ejemplos:
Entrada: arr[] = {2, 5}, K = 4
Salida: 14
Explicación:
Realice las siguientes operaciones para maximizar la suma:
Operación 1: Seleccione 5, luego redúzcalo, de modo que la nueva array se convierta en {2, 4}.
Operación 2: seleccione 4, luego redúzcalo, de modo que la nueva array se convierta en {2, 3}.
Operación 3: seleccione 3, luego redúzcalo, de modo que la nueva array se convierta en {2, 2}.
Operación 4: seleccione 2, luego redúzcalo, de modo que la nueva array se convierta en {2, 1}.
Por tanto, la suma máxima es 5 + 4 + 3 + 2 = 14.Entrada: arr[] = {2, 8, 4, 10, 6}, K = 2
Salida: 19
Explicación:
Realice las siguientes operaciones para maximizar la suma:
Operación 1: seleccione 10, luego redúzcalo, de modo que la nueva array se convierta en { 2, 8, 4, 9, 6}.
Operación 2: seleccione 9, luego redúzcalo, de modo que la nueva array se convierta en {2, 8, 4, 8, 6}.
Por tanto, la suma máxima es 10 + 9 = 19.
Enfoque ingenuo: el enfoque más simple es usar Max Heap para elegir el elemento máximo cada vez. Agregue el elemento máximo a la suma y elimínelo del Max Heap y agregue (elemento máximo – 1) . Realice esta operación K e imprima la suma.
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 find maximum possible
// after adding elements K times and
// decrementing each added value by 1
long maxSum(vector<int> arr, int k)
{
// Stores the maximum sum
long max_sum = 0;
// Create max_heap to get
// the maximum element
priority_queue<int> max_heap;
// Update the max_heap
for(int t : arr)
max_heap.push(t);
// Calculate the max_sum
while (k-- > 0)
{
int tmp = max_heap.top();
max_heap.pop();
max_sum += tmp;
max_heap.push(tmp - 1);
}
// Return the maximum sum
return max_sum;
}
// Driver code
int main()
{
// Given an array arr[]
vector<int> arr = { 2, 5 };
// Given K
int K = 4;
// Function Call
cout << maxSum(arr, K);
}
// This code is contributed by mohit kumar 29
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find maximum possible
// after adding elements K times and
// decrementing each added value by 1
public static long maxSum(int[] arr,
int k)
{
// Stores the maximum sum
long max_sum = 0;
// Create max_heap to get
// the maximum element
PriorityQueue<Integer> max_heap
= new PriorityQueue<>(
Collections.reverseOrder());
// Update the max_heap
for (int t : arr)
max_heap.add(t);
// Calculate the max_sum
while (k-- > 0) {
int tmp = max_heap.poll();
max_sum += tmp;
max_heap.add(tmp - 1);
}
// Return the maximum sum
return max_sum;
}
// Driver Code
public static void main(String[] args)
{
// Given an array arr[]
int[] arr = { 2, 5 };
// Given K
int K = 4;
// Function Call
System.out.println(maxSum(arr, K));
}
}
Python3
# Python3 program for the above approach # Function to find maximum possible # after adding elements K times and # decrementing each added value by 1 from heapq import heappop, heappush, heapify def maxSum(arr, k): # Stores the maximum sum max_sum = 0 # Create max_heap to get # the maximum element max_heap = [] heapify(max_heap) # Update the max_heap for i in range(len(arr) - 1, 0, -1): heappush(max_heap, arr[i]) # Calculate the max_sum while (k > 0): tmp = heappop(max_heap) max_sum += tmp #max_heap.put(tmp - 1); heappush(max_heap, tmp - 1) k -= 1 # Return the maximum sum return max_sum # Driver Code if __name__ == '__main__': # Given an array arr arr = [ 2, 5 ] # Given K K = 4 # Function Call print(maxSum(arr, K)) # This code is contributed by gauravrajput1
C#
// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find maximum possible
// after adding elements K times and
// decrementing each added value by 1
public static long maxSum(int[] arr, int k)
{
// Stores the maximum sum
long max_sum = 0;
// Create max_heap to get
// the maximum element
List<int> max_heap = new List<int>();
// Update the max_heap
foreach(int t in arr) max_heap.Add(t);
max_heap.Sort();
max_heap.Reverse();
// Calculate the max_sum
while (k-- > 1)
{
int tmp = max_heap[0];
max_heap.Remove(0);
max_sum += tmp;
max_heap.Add(tmp - 1);
max_heap.Sort();
max_heap.Reverse();
}
// Return the maximum sum
return max_sum - 1;
}
// Driver Code
public static void Main(String[] args)
{
// Given an array []arr
int[] arr = { 2, 5 };
// Given K
int K = 4;
// Function Call
Console.WriteLine(maxSum(arr, K));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program for the above approach
// Function to find maximum possible
// after adding elements K times and
// decrementing each added value by 1
function maxSum(arr, k)
{
// Stores the maximum sum
let max_sum = 0;
// Create max_heap to get
// the maximum element
let max_heap = [];
// Update the max_heap
for(let t = 0; t < arr.length; t++)
max_heap.push(arr[t]);
max_heap.sort(function(a, b){return b - a;});
// Calculate the max_sum
while (k-- > 0)
{
let tmp = max_heap.shift();
max_sum += tmp;
max_heap.push(tmp - 1);
max_heap.sort(function(a, b){return b - a;});
}
// Return the maximum sum
return max_sum;
}
// Driver Code
// Given an array arr[]
let arr = [ 2, 5 ];
// Given K
let K = 4;
// Function Call
document.write(maxSum(arr, K));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
14
Complejidad de tiempo: O(K*log(N)), donde N es la longitud de la array dada y K es el número dado de operaciones.
Espacio Auxiliar: O(N)
Enfoque eficiente: la idea es utilizar el concepto Hashing almacenando la frecuencia de cada elemento de la array dada . Siga los pasos a continuación para resolver el problema:
- Cree freq[] de tamaño M + 1 donde M es el elemento máximo presente en la array dada y una variable max_sum para almacenar la frecuencia de cada elemento de arr[] y la suma máxima posible respectivamente.
- Atraviese la array freq[] de derecha a izquierda, es decir, de i = M a 0 .
- Incremente max_sum por freq[i]*i , reduzca K por freq[i] e incremente freq[i – 1] por freq[i] , si K ≥ freq[i] .
- De lo contrario, incremente max_sum en i*K y rompa el bucle porque K se convierte en 0 .
- Devuelve max_sum como la suma máxima posible.
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 find maximum possible
// after adding elements K times and
// decrementing each added value by 1
long maxSum(int arr[], int k, int n)
{
// Stores the maximum sum
long max_sum = 0;
// Stores frequency of element
int freq[100000 + 1] = {0};
// Update frequency of array element
for(int i = 0; i < n; i++)
freq[arr[i]]++;
// Traverse from right to left in
// freq[] to find maximum sum
for(int i = 100000; i > 0; i--)
{
if (k >= freq[i])
{
// Update max_sum
max_sum += i * freq[i];
// Decrement k
k -= freq[i];
freq[i - 1] += freq[i];
}
// Update max_sum and break
else
{
max_sum += i * k;
break;
}
}
// Return the maximum sum
return max_sum;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 2, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
// Given K
int K = 4;
// Function Call
cout << (maxSum(arr, K, n));
return 0;
}
// This code is contributed by chitranayal
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find maximum possible
// after adding elements K times and
// decrementing each added value by 1
public static long maxSum(int[] arr,
int k)
{
// Stores the maximum sum
long max_sum = 0;
// Stores frequency of element
int[] freq = new int[100000 + 1];
// Update frequency of array element
for (int t : arr)
freq[t]++;
// Traverse from right to left in
// freq[] to find maximum sum
for (int i = 100000; i > 0; i--) {
if (k >= freq[i]) {
// Update max_sum
max_sum += i * freq[i];
// Decrement k
k -= freq[i];
freq[i - 1] += freq[i];
}
// Update max_sum and break
else {
max_sum += i * k;
break;
}
}
// Return the maximum sum
return max_sum;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int[] arr = { 2, 5 };
// Given K
int K = 4;
// Function Call
System.out.println(maxSum(arr, K));
}
}
Python3
# Python program for the above approach # Function to find maximum possible # after adding elements K times and # decrementing each added value by 1 def maxSum(arr, k): # Stores the maximum sum max_sum = 0; # Stores frequency of element freq = [0]*(100000 + 1); # Update frequency of array element for i in range(len(arr)): freq[arr[i]] += 1; # Traverse from right to left in # freq to find maximum sum for i in range(100000, 1, -1): if (k >= freq[i]): # Update max_sum max_sum += i * freq[i]; # Decrement k k -= freq[i]; freq[i - 1] += freq[i]; # Update max_sum and break else: max_sum += i * k; break; # Return the maximum sum return max_sum; # Driver Code if __name__ == '__main__': # Given array arr arr = [2, 5]; # Given K K = 4; # Function Call print(maxSum(arr, K)); # This code contributed by gauravrajput1
C#
// C# program for the
// above approach
using System;
class GFG{
// Function to find maximum possible
// after adding elements K times and
// decrementing each added value by 1
public static long maxSum(int[] arr,
int k)
{
// Stores the maximum
// sum
long max_sum = 0;
// Stores frequency of
// element
int[] freq =
new int[100000 + 1];
// Update frequency of
// array element
foreach (int t in arr)
{
freq[t]++;
}
// Traverse from right to
// left in []freq to find
// maximum sum
for (int i = 100000; i > 0; i--)
{
if (k >= freq[i])
{
// Update max_sum
max_sum += i * freq[i];
// Decrement k
k -= freq[i];
freq[i - 1] += freq[i];
}
// Update max_sum and
// break
else
{
max_sum += i * k;
break;
}
}
// Return the maximum
// sum
return max_sum;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int[] arr = {2, 5};
// Given K
int K = 4;
// Function Call
Console.WriteLine(
maxSum(arr, K));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
//Javascript program for the above approach
// Function to find maximum possible
// after adding elements K times and
// decrementing each added value by 1
function maxSum(arr, k, n)
{
// Stores the maximum sum
var max_sum = 0;
// Stores frequency of element
var freq = new Array(100000 + 1);
freq.fill(0);
// Update frequency of array element
for(var i = 0; i < n; i++)
freq[arr[i]]++;
// Traverse from right to left in
// freq[] to find maximum sum
for(var i = 100000; i > 0; i--)
{
if (k >= freq[i])
{
// Update max_sum
max_sum += i * freq[i];
// Decrement k
k -= freq[i];
freq[i - 1] += freq[i];
}
// Update max_sum and break
else
{
max_sum += i * k;
break;
}
}
// Return the maximum sum
return max_sum;
}
var arr = [ 2, 5 ];
var n = arr.length;
// Given K
var K = 4;
// Function Call
document.write (maxSum(arr, K, n));
// This code is contributed by SoumikMondal
</script>
Producción:
14
Complejidad de tiempo: O(N), donde N es la longitud de la array dada.
Espacio auxiliar: O (max (arr)) ya que tomamos freq hashmap de tamaño igual al elemento máximo de la array dada.
Sería mejor usar esta solución cuando el tamaño (array) y el máximo (array) son del mismo orden.