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>
Producción:
Maximum Profit = 100
Complejidad temporal: O(N)
Espacio auxiliar: O(1)