Dada una array de precios [] que denota los precios de las acciones en diferentes días, la tarea es encontrar la máxima ganancia posible después de comprar y vender las acciones en diferentes días utilizando transacciones donde se permiten dos transacciones como máximo.
Nota: no puede participar en varias transacciones al mismo tiempo (es decir, debe vender las acciones antes de volver a comprar).
Ejemplos:
Entrada: precios[] = {3, 3, 5, 0, 0, 3, 1, 4}
Salida: 6
Explicación:
Compre el día 4 y venda el día 6 => Beneficio = 3 – 0 = 3
Compre el día 7 y Vender en el día 8 => Beneficio = 4 -1 = 3
Por lo tanto, Beneficio total = 3 + 3 = 6Entrada: precios[] = {1, 2, 3, 4, 5}
Salida: 4
Explicación:
Compre el día 1 y venda el día 6 => Beneficio = 5 -1 = 4
Por lo tanto, Beneficio total = 4
Ya hemos discutido este problema usando Programación Dinámica en el espacio O(N) en este artículo.
Enfoque eficiente: la idea utilizada aquí es realizar un seguimiento de las dos transacciones al mismo tiempo. La ganancia de las dos acciones se calcula de la siguiente manera
- Beneficio máximo para la primera transacción
- Encuentre el precio mínimo que tenemos que pagar de nuestro bolsillo (comprar 1) para obtener la primera acción, que es el precio de la acción en ese día o en cualquier día anterior.
- Encuentre la ganancia máxima vendiendo la primera acción del día actual.
- Beneficio máximo para la segunda Transacción
- El precio mínimo que tendremos que pagar de nuestro bolsillo para comprar acciones de segunda mano será
buy2 = price[i] - profit1, // Profit 1 is the profit from // selling the first stock
- Encuentre la ganancia máxima (beneficio2) vendiendo la segunda acción.
Explicación con ejemplo:
Tomemos precio[] = { 3, 5, 4, 5}
Compramos la primera acción el día 1
compra1 = 3.
Vendemos la primera acción el día 2.
ganancia1 = 5 – 3 = 2. Obtendremos
una ganancia de 2 después de comprar la acción el primer día y venderla el segundo día.
Entonces, ganancia1 = 2
Ahora compraremos la segunda acción el tercer día . El
precio de la acción el tercer día es 4.
Como ya obtuvimos una ganancia de 2, gastaremos solo 2 extra de nuestro paquete para comprar la acción
, es decir, (4 – ganancia1 ) = 2
comprar2 = 2
Ahora, venderemos la segunda acción el día 4. El
precio de la acción el 4to día es 5.
ganancia2 = 5 – compra2 = 5 – 2 = 3.
Ahora, podemos ver que la ganancia final incluye la ganancia de compra y venta de dos acciones
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implmenetation to find // maximum possible profit // with at most two transactions #include <bits/stdc++.h> using namespace std; // Function to find the maximum // profit with two transactions // on a given list of stock prices int maxProfit(int price[], int n) { // buy1 - Money lent to buy 1 stock // profit1 - Profit after selling // the 1st stock buyed. // buy2 - Money lent to buy 2 stocks // including profit of selling 1st stock // profit2 - Profit after selling 2 stocks int buy1, profit1, buy2, profit2; // Set initial buying values to // INT_MAX as we want to minimize it buy1 = buy2 = INT_MAX; // Set initial selling values to // zero as we want to maximize it profit1 = profit2 = 0; for (int i = 0; i < n; i++) { // Money lent to buy the stock // should be minimum as possible. // buy1 tracks the minimum possible // stock to buy from 0 to i-1. buy1 = min(buy1, price[i]); // Profit after selling a stock // should be maximum as possible. // profit1 tracks maximum possible // profit we can make from 0 to i-1. profit1 = max(profit1, price[i] - buy1); // Now for buying the 2nd stock, // we will integrate profit made // from selling the 1st stock buy2 = min(buy2, price[i] - profit1); // Profit after selling a 2 stocks // should be maximum as possible. // profit2 tracks maximum possible // profit we can make from 0 to i-1. profit2 = max(profit2, price[i] - buy2); } return profit2; } // Driver Code int main() { int price[] = { 2, 30, 15, 10, 8, 25, 80 }; int n = sizeof(price) / sizeof(price[0]); cout << "Maximum Profit = " << maxProfit(price, n); return 0; }
Java
// Java implmenetation to find // maximum possible profit // with at most two transactions import java.util.*; class GFG{ // Function to find the maximum // profit with two transactions // on a given list of stock prices static int maxProfit(int price[], int n) { // buy1 - Money lent to buy 1 stock // profit1 - Profit after selling // the 1st stock buyed. // buy2 - Money lent to buy 2 stocks // including profit of selling 1st stock // profit2 - Profit after selling 2 stocks int buy1, profit1, buy2, profit2; // Set initial buying values to // Integer.MAX_VALUE as we want to // minimize it buy1 = buy2 = Integer.MAX_VALUE; // Set initial selling values to // zero as we want to maximize it profit1 = profit2 = 0; for(int i = 0; i < n; i++) { // Money lent to buy the stock // should be minimum as possible. // buy1 tracks the minimum possible // stock to buy from 0 to i-1. buy1 = Math.min(buy1, price[i]); // Profit after selling a stock // should be maximum as possible. // profit1 tracks maximum possible // profit we can make from 0 to i-1. profit1 = Math.max(profit1, price[i] - buy1); // Now for buying the 2nd stock, // we will integrate profit made // from selling the 1st stock buy2 = Math.min(buy2, price[i] - profit1); // Profit after selling a 2 stocks // should be maximum as possible. // profit2 tracks maximum possible // profit we can make from 0 to i-1. profit2 = Math.max(profit2, price[i] - buy2); } return profit2; } // Driver Code public static void main(String[] args) { int price[] = { 2, 30, 15, 10, 8, 25, 80 }; int n = price.length; System.out.print("Maximum Profit = " + maxProfit(price, n)); } } // This code is contributed by Rajput-Ji
Python3
# Python3 implmenetation to find # maximum possible profit # with at most two transactions import sys # Function to find the maximum # profit with two transactions # on a given list of stock prices def maxProfit(price, n): # buy1 - Money lent to buy 1 stock # profit1 - Profit after selling # the 1st stock buyed. # buy2 - Money lent to buy 2 stocks # including profit of selling 1st stock # profit2 - Profit after selling 2 stocks # Set initial buying values to # INT_MAX as we want to minimize it buy1, buy2 = sys.maxsize, sys.maxsize # Set initial selling values to # zero as we want to maximize it profit1, profit2 = 0, 0 for i in range(n): # Money lent to buy the stock # should be minimum as possible. # buy1 tracks the minimum possible # stock to buy from 0 to i-1. buy1 = min(buy1, price[i]) # Profit after selling a stock # should be maximum as possible. # profit1 tracks maximum possible # profit we can make from 0 to i-1. profit1 = max(profit1, price[i] - buy1) # Now for buying the 2nd stock, # we will integrate profit made # from selling the 1st stock buy2 = min(buy2, price[i] - profit1) # Profit after selling a 2 stocks # should be maximum as possible. # profit2 tracks maximum possible # profit we can make from 0 to i-1. profit2 = max(profit2, price[i] - buy2) return profit2 # Driver code price = [ 2, 30, 15, 10, 8, 25, 80 ] n = len(price) print("Maximum Profit = ", maxProfit(price, n)) # This code is contributed by divyeshrabadiya07
C#
// C# implmenetation to find // maximum possible profit // with at most two transactions using System; class GFG{ // Function to find the maximum // profit with two transactions // on a given list of stock prices static int maxProfit(int []price, int n) { // buy1 - Money lent to buy 1 stock // profit1 - Profit after selling // the 1st stock buyed. // buy2 - Money lent to buy 2 stocks // including profit of selling 1st stock // profit2 - Profit after selling 2 stocks int buy1, profit1, buy2, profit2; // Set initial buying values to // int.MaxValue as we want to // minimize it buy1 = buy2 = int.MaxValue; // Set initial selling values to // zero as we want to maximize it profit1 = profit2 = 0; for(int i = 0; i < n; i++) { // Money lent to buy the stock // should be minimum as possible. // buy1 tracks the minimum possible // stock to buy from 0 to i-1. buy1 = Math.Min(buy1, price[i]); // Profit after selling a stock // should be maximum as possible. // profit1 tracks maximum possible // profit we can make from 0 to i-1. profit1 = Math.Max(profit1, price[i] - buy1); // Now for buying the 2nd stock, // we will integrate profit made // from selling the 1st stock buy2 = Math.Min(buy2, price[i] - profit1); // Profit after selling a 2 stocks // should be maximum as possible. // profit2 tracks maximum possible // profit we can make from 0 to i-1. profit2 = Math.Max(profit2, price[i] - buy2); } return profit2; } // Driver Code public static void Main(String[] args) { int []price = { 2, 30, 15, 10, 8, 25, 80 }; int n = price.Length; Console.Write("Maximum Profit = " + maxProfit(price, n)); } } // This code is contributed by Rajput-Ji
Javascript
<script> // javascript implmenetation to find // maximum possible profit // with at most two transactions // Function to find the maximum // profit with two transactions // on a given list of stock prices function maxProfit(price , n) { // buy1 - Money lent to buy 1 stock // profit1 - Profit after selling // the 1st stock buyed. // buy2 - Money lent to buy 2 stocks // including profit of selling 1st stock // profit2 - Profit after selling 2 stocks var buy1, profit1, buy2, profit2; // Set initial buying values to // Number.MAX_VALUE as we want to // minimize it buy1 = buy2 = Number.MAX_VALUE; // Set initial selling values to // zero as we want to maximize it profit1 = profit2 = 0; for (i = 0; i < n; i++) { // Money lent to buy the stock // should be minimum as possible. // buy1 tracks the minimum possible // stock to buy from 0 to i-1. buy1 = Math.min(buy1, price[i]); // Profit after selling a stock // should be maximum as possible. // profit1 tracks maximum possible // profit we can make from 0 to i-1. profit1 = Math.max(profit1, price[i] - buy1); // Now for buying the 2nd stock, // we will integrate profit made // from selling the 1st stock buy2 = Math.min(buy2, price[i] - profit1); // Profit after selling a 2 stocks // should be maximum as possible. // profit2 tracks maximum possible // profit we can make from 0 to i-1. profit2 = Math.max(profit2, price[i] - buy2); } return profit2; } // Driver Code var price = [ 2, 30, 15, 10, 8, 25, 80 ]; var n = price.length; document.write("Maximum Profit = " + maxProfit(price, n)); // This code is contributed by todaysgaurav. </script>
Maximum Profit = 100
Complejidad temporal: O(N)
Espacio auxiliar: O(1)