Dado un entero K y un arreglo arr[] que consta de N enteros, donde un elemento del arreglo arr[i] representa el precio del i – ésimo libro. El beneficio de comprar i – ésimo libro representa max(0, -1 * arr[i]) , la tarea es encontrar el máximo beneficio posible comprando como máximo K libros.
Ejemplos:
Entrada: arr[] = {-10, 20, -30, 50, -19}, K = 2
Salida: 49
Explicación:
Se puede obtener la máxima ganancia comprando los libros arr[2](= -30). Ganancia = 30 y el libro, arr[4](= -19) por la ganancia de 19.
Por lo tanto, la ganancia máxima total obtenida es, (30+19 = 49).Entrada: arr[] = {10, 20, 16, 25}, K = 3
Salida: 0
Enfoque: el problema se puede resolver utilizando el enfoque codicioso basado en la observación de que solo los libros con precios negativos contribuyen al máximo beneficio. Siga los pasos a continuación para resolver este problema:
- Ordene la array arr[] en orden ascendente .
- Inicialice una variable, digamos, maxBenefit como 0 para almacenar la ganancia máxima.
- Iterar en el rango [0, N-1] usando la variable i y realizar los siguientes pasos:
- Si K es mayor que 0 y arr[i] es negativo, agregue abs(arr[i]) a maxBenefit y luego reduzca el valor de K en 1.
- Finalmente, imprima el valor de maxBenefit como la máxima ganancia obtenida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum
// profit that can be obtained
// by buying at most K books
int maxProfit(int arr[], int N, int K)
{
// Sort the array in
// ascending order
sort(arr, arr + N);
// Stores the maximum profit
int maxBenefit = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// If arr[i] is less than 0
// and K is greater than 0
if (arr[i] < 0 && K > 0) {
// Increment the maxBenefit
// by abs(arr[i])
maxBenefit += abs(arr[i]);
// Decrement K by 1
K--;
}
}
// Return the profit
return maxBenefit;
}
// Driver Code
int main()
{
// Given Input
int arr[] = { -10, 20, -30, 50, -19 };
int K = 2;
int N = sizeof(arr) / sizeof(int);
// Function call
cout << maxProfit(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.Arrays;
class GFG
{
// Function to find the maximum
// profit that can be obtained
// by buying at most K books
public static int maxProfit(int arr[], int N, int K)
{
// Sort the array in
// ascending order
Arrays.sort(arr);
// Stores the maximum profit
int maxBenefit = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// If arr[i] is less than 0
// and K is greater than 0
if (arr[i] < 0 && K > 0) {
// Increment the maxBenefit
// by abs(arr[i])
maxBenefit += Math.abs(arr[i]);
// Decrement K by 1
K--;
}
}
// Return the profit
return maxBenefit;
}
// Driver Code
public static void main(String[] args)
{
// Given input
int arr[] = { -10, 20, -30, 50, -19 };
int K = 2;
int N = 5;
// Function call
int res = maxProfit(arr, N, K);
System.out.println(res);
}
}
// This code is contributed by lokeshpotta20.
Python3
# Python3 program for above approach # Function to find the maximum # profit that can be obtained # by buying at most K books def maxProfit(arr, N, K): # Sort the array in # ascending order arr.sort() # Stores the maximum profit maxBenefit = 0 # Traverse the array arr[] for i in range(0, N, 1): # If arr[i] is less than 0 # and K is greater than 0 if (arr[i] < 0 and K > 0): # Increment the maxBenefit # by abs(arr[i]) maxBenefit += abs(arr[i]) # Decrement K by 1 K -= 1 # Return the profit return maxBenefit # Driver Code if __name__ == '__main__': # Given Input arr = [ -10, 20, -30, 50, -19 ] K = 2 N = len(arr) # Function call print(maxProfit(arr, N, K)) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
class GFG {
// Function to find the maximum
// profit that can be obtained
// by buying at most K books
public static int maxProfit(int[] arr, int N, int K)
{
// Sort the array in
// ascending order
Array.Sort(arr);
// Stores the maximum profit
int maxBenefit = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// If arr[i] is less than 0
// and K is greater than 0
if (arr[i] < 0 && K > 0) {
// Increment the maxBenefit
// by abs(arr[i])
maxBenefit += Math.Abs(arr[i]);
// Decrement K by 1
K--;
}
}
// Return the profit
return maxBenefit;
}
// Driver Code
public static void Main()
{
// Given input
int[] arr = { -10, 20, -30, 50, -19 };
int K = 2;
int N = 5;
// Function call
int res = maxProfit(arr, N, K);
Console.Write(res);
}
}
// This code is contributed by subhammahato348.
Javascript
<script>
// JavaScript program for above approach
// Function to find the maximum
// profit that can be obtained
// by buying at most K books
function maxProfit(arr, N, K) {
// Sort the array in
// ascending order
arr.sort(function (a, b) { return a - b });
// Stores the maximum profit
var maxBenefit = 0;
// Traverse the array arr[]
for (let i = 0; i < N; i++) {
// If arr[i] is less than 0
// and K is greater than 0
if (arr[i] < 0 && K > 0) {
// Increment the maxBenefit
// by abs(arr[i])
maxBenefit += Math.abs(arr[i]);
// Decrement K by 1
K--;
}
}
// Return the profit
return maxBenefit;
}
// Driver Code
// Given Input
var arr = [-10, 20, -30, 50, -19];
var K = 2;
var N = 5;
// Function call
document.write(maxProfit(arr, N, K));
// This code is contributed by lokeshpotta20.
</script>
49
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por hrithikgarg03188 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA