Tipo I: Se permite como máximo una transacción
Dada una array de precios [] de longitud N , que representa los precios de las acciones en diferentes días, la tarea es encontrar la máxima ganancia posible para comprar y vender las acciones en diferentes días utilizando transacciones en las que se permite como máximo una transacción.
Nota: Las acciones deben comprarse antes de venderse.
Ejemplos:
Entrada: precios[] = {7, 1, 5, 3, 6, 4]
Salida: 5
Explicación:
El precio más bajo de la acción es el 2º día, es decir, precio = 1. A partir del 2º día, el precio más alto el precio de la acción se observa el día 5 , es decir, el precio = 6.
Por lo tanto, la ganancia máxima posible = 6 – 1 = 5.Entrada: precios[] = {7, 6, 4, 3, 1}
Salida: 0
Explicación: Dado que la array está en orden decreciente, no existe forma posible de resolver el problema.
Enfoque 1:
este problema se puede resolver utilizando el enfoque codicioso. Para maximizar la ganancia tenemos que minimizar el costo de compra y tenemos que venderlo al precio máximo.
Siga los pasos a continuación para implementar la idea anterior:
- Declare una variable de compra para almacenar el costo de compra y max_profit para almacenar la ganancia máxima.
- Inicialice la variable de compra en el primer elemento de la array de precios .
- Itere sobre la array de precios y verifique si el precio actual es mínimo o no.
- Si el precio actual es mínimo entonces compre en este enésimo día.
- Si el precio actual es mayor que el de la compra anterior, obtenga ganancias y maximice el max_profit.
- Finalmente, devuelve max_profit .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <iostream>
using namespace std;
int maxProfit(int prices[], int n)
{
int buy = prices[0], max_profit = 0;
for (int i = 1; i < n; i++) {
// Checking for lower buy value
if (buy > prices[i])
buy = prices[i];
// Checking for higher profit
else if (prices[i] - buy > max_profit)
max_profit = prices[i] - buy;
}
return max_profit;
}
// Driver Code
int main()
{
int prices[] = { 7, 1, 5, 6, 4 };
int n = sizeof(prices) / sizeof(prices[0]);
int max_profit = maxProfit(prices, n);
cout << max_profit << endl;
return 0;
}
Java
// Java code for the above approach
class GFG {
static int maxProfit(int prices[], int n)
{
int buy = prices[0], max_profit = 0;
for (int i = 1; i < n; i++) {
// Checking for lower buy value
if (buy > prices[i])
buy = prices[i];
// Checking for higher profit
else if (prices[i] - buy > max_profit)
max_profit = prices[i] - buy;
}
return max_profit;
}
// Driver Code
public static void main(String args[])
{
int prices[] = { 7, 1, 5, 6, 4 };
int n = prices.length;
int max_profit = maxProfit(prices, n);
System.out.println(max_profit);
}
}
// This code is contributed by Lovely Jain
Python3
## Python program for the above approach: def maxProfit(prices, n): buy = prices[0] max_profit = 0 for i in range(1, n): ## Checking for lower buy value if (buy > prices[i]): buy = prices[i] ## Checking for higher profit elif (prices[i] - buy > max_profit): max_profit = prices[i] - buy; return max_profit; ## Driver code if __name__=='__main__': prices = [ 7, 1, 5, 6, 4 ]; n = len(prices) max_profit = maxProfit(prices, n); print(max_profit)
Producción :
5
Complejidad temporal: O(N). Donde N es el tamaño de la array de precios.
Espacio Auxiliar: O(1). No utilizamos ningún espacio adicional.
Enfoque 2: El problema dado se puede resolver con base en la idea de encontrar la diferencia máxima entre dos elementos de array con el número más pequeño antes del número más grande . Por lo tanto, este problema se puede reducir a encontrar max(prices[j]−prices[i]) para cada par de índices i y j, tal que j>i .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function to find maximum profit possible
// by buying and selling at most one stack
int findMaximumProfit(vector<int>& prices, int i, int k,
bool buy, vector<vector<int> >& v)
{
// If no stock can be chosen
if (i >= prices.size() || k <= 0)
return 0;
if (v[i][buy] != -1)
return v[i][buy];
// If a stock is already bought
if (buy) {
return v[i][buy]
= max(-prices[i]
+ findMaximumProfit(prices, i + 1,
k, !buy, v),
findMaximumProfit(prices, i + 1, k,
buy, v));
}
// Otherwise
else {
// Buy now
return v[i][buy]
= max(prices[i]
+ findMaximumProfit(
prices, i + 1, k - 1, !buy, v),
findMaximumProfit(prices, i + 1, k,
buy, v));
}
}
// Function to find the maximum
// profit in the buy and sell stock
int maxProfit(vector<int>& prices)
{
int n = prices.size();
vector<vector<int> > v(n, vector<int>(2, -1));
// buy = 1 because atmost one
// transaction is allowed
return findMaximumProfit(prices, 0, 1, 1, v);
}
// Driver Code
int main()
{
// Given prices
vector<int> prices = { 7, 1, 5, 3, 6, 4 };
// Function Call to find the
// maximum profit possible by
// buying and selling a single stock
int ans = maxProfit(prices);
// Print answer
cout << ans << endl;
return 0;
}
Java
// Java code for the above approach
import java.util.*;
class GFG {
// Function to find maximum profit possible
// by buying and selling at most one stack
static int findMaximumProfit(int[] prices, int i, int k,
int buy, int[][] v)
{
// If no stock can be chosen
if (i >= prices.length || k <= 0)
return 0;
if (v[i][buy] != -1)
return v[i][buy];
// If a stock is already bought
// Buy now
int nbuy;
if (buy == 1)
nbuy = 0;
else
nbuy = 1;
if (buy == 1) {
return v[i][buy] = Math.max(
-prices[i]
+ findMaximumProfit(
prices, i + 1, k, nbuy, v),
findMaximumProfit(prices, i + 1, k,
(int)(buy), v));
}
// Otherwise
else {
// Buy now
if (buy == 1)
nbuy = 0;
else
nbuy = 1;
return v[i][buy]
= Math.max(
prices[i]
+ findMaximumProfit(prices, i + 1,
k - 1, nbuy, v),
findMaximumProfit(prices, i + 1, k, buy,
v));
}
}
// Function to find the maximum
// profit in the buy and sell stock
static int maxProfit(int[] prices)
{
int n = prices.length;
int[][] v = new int[n][2];
for (int i = 0; i < v.length; i++) {
v[i][0] = -1;
v[i][1] = -1;
}
// buy = 1 because atmost one
// transaction is allowed
return findMaximumProfit(prices, 0, 1, 1, v);
}
// Driver Code
public static void main(String[] args)
{
// Given prices
int[] prices = { 7, 1, 5, 3, 6, 4 };
// Function Call to find the
// maximum profit possible by
// buying and selling a single stock
int ans = maxProfit(prices);
// Print answer
System.out.println(ans);
}
// This code is contributed by Potta Lokesh
Python3
# Python 3 program for the above approach # Function to find maximum profit possible # by buying and selling at most one stack def findMaximumProfit(prices, i, k, buy, v): # If no stock can be chosen if (i >= len(prices) or k <= 0): return 0 if (v[i][buy] != -1): return v[i][buy] # If a stock is already bought if (buy): v[i][buy] = max(-prices[i] + findMaximumProfit(prices, i + 1, k, not buy, v), findMaximumProfit(prices, i + 1, k, buy, v)) return v[i][buy] # Otherwise else: # Buy now v[i][buy] = max(prices[i] + findMaximumProfit( prices, i + 1, k - 1, not buy, v), findMaximumProfit(prices, i + 1, k, buy, v)) return v[i][buy] # Function to find the maximum # profit in the buy and sell stock def maxProfit(prices): n = len(prices) v = [[-1 for x in range(2)]for y in range(n)] # buy = 1 because atmost one # transaction is allowed return findMaximumProfit(prices, 0, 1, 1, v) # Driver Code if __name__ == "__main__": # Given prices prices = [7, 1, 5, 3, 6, 4] # Function Call to find the # maximum profit possible by # buying and selling a single stock ans = maxProfit(prices) # Print answer print(ans)
C#
// C# program for above approach
using System;
class GFG {
// Function to find maximum profit possible
// by buying and selling at most one stack
static int findMaximumProfit(int[] prices, int i, int k,
int buy, int[, ] v)
{
// If no stock can be chosen
if (i >= prices.Length || k <= 0)
return 0;
if (v[i, buy] != -1)
return v[i, buy];
// If a stock is already bought
// Buy now
int nbuy;
if (buy == 1)
nbuy = 0;
else
nbuy = 1;
if (buy == 1) {
return v[i, buy] = Math.Max(
-prices[i]
+ findMaximumProfit(
prices, i + 1, k, nbuy, v),
findMaximumProfit(prices, i + 1, k,
(int)(buy), v));
}
// Otherwise
else {
// Buy now
if (buy == 1)
nbuy = 0;
else
nbuy = 1;
return v[i, buy]
= Math.Max(
prices[i]
+ findMaximumProfit(prices, i + 1,
k - 1, nbuy, v),
findMaximumProfit(prices, i + 1, k, buy,
v));
}
}
// Function to find the maximum
// profit in the buy and sell stock
static int maxProfit(int[] prices)
{
int n = prices.Length;
int[, ] v = new int[n, 2];
for (int i = 0; i < n; i++) {
v[i, 0] = -1;
v[i, 1] = -1;
}
// buy = 1 because atmost one
// transaction is allowed
return findMaximumProfit(prices, 0, 1, 1, v);
}
// Driver Code
public static void Main()
{
// Given prices
int[] prices = { 7, 1, 5, 3, 6, 4 };
// Function Call to find the
// maximum profit possible by
// buying and selling a single stock
int ans = maxProfit(prices);
// Print answer
Console.Write(ans);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript code for the above approach
// Function to find maximum profit possible
// by buying and selling at most one stack
function findMaximumProfit(prices, i, k, buy, v) {
// If no stock can be chosen
if (i >= prices.length || k <= 0)
return 0;
if (v[i][buy] != -1)
return v[i][buy];
// If a stock is already bought
// Buy now
let nbuy;
if (buy == 1)
nbuy = 0;
else
nbuy = 1;
if (buy == 1) {
return v[i][buy] = Math.max(-prices[i] +
findMaximumProfit(prices, i + 1, k, nbuy, v),
findMaximumProfit(prices, i + 1, k, buy, v));
}
// Otherwise
else {
// Buy now
if (buy == 1)
nbuy = 0;
else
nbuy = 1;
return v[i][buy] = Math.max(prices[i] +
findMaximumProfit(prices, i + 1, k - 1, nbuy, v),
findMaximumProfit(prices, i + 1, k, buy, v));
}
}
// Function to find the maximum
// profit in the buy and sell stock
function maxProfit(prices) {
let n = prices.length;
let v = new Array(n).fill(0).map(() => new Array(2).fill(-1))
// buy = 1 because atmost one
// transaction is allowed
return findMaximumProfit(prices, 0, 1, 1, v);
}
// Driver Code
// Given prices
let prices = [7, 1, 5, 3, 6, 4];
// Function Call to find the
// maximum profit possible by
// buying and selling a single stock
let ans = maxProfit(prices);
// Print answer
document.write(ans);
// This code is contributed by Saurabh Jaiswal
</script>
5
Complejidad de tiempo: O(N) donde N es la longitud de la array dada.
Espacio Auxiliar: O(N)
Tipo II: se permiten transacciones infinitas
Dada una array price[] de longitud N , que representa los precios de las acciones en diferentes días, la tarea es encontrar la máxima ganancia posible para comprar y vender acciones en diferentes días utilizando transacciones en las que se permite cualquier número de transacciones.
Ejemplos:
Entrada: precios[] = {7, 1, 5, 3, 6, 4}
Salida: 7
Explicación:
Compra el 2º día. Precio = 1.
Vender el 3er día . Precio = 5.
Por lo tanto, beneficio = 5 – 1 = 4.
Compra el 4º día. Precio = 3.
Vender el 5º día . Precio = 6.
Por lo tanto, ganancia = 4 + (6 – 3) = 7.Entrada: precios = {1, 2, 3, 4, 5}
Salida: 4
Explicación:
Compra el 1er día. Precio = 1.
Vender el 5° día. Precio = 5.
Por lo tanto, beneficio = 5 – 1 = 4.
Enfoque: la idea es mantener un valor booleano que indique si hay alguna compra en curso o no. En caso afirmativo, en el estado actual, las acciones se pueden vender para maximizar las ganancias o pasar al siguiente precio sin vender las acciones. De lo contrario, si no se realiza ninguna transacción, se pueden comprar las acciones actuales o pasar al siguiente precio sin comprar .
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 calculate maximum
// profit possible by buying or
// selling stocks any number of times
int find(int ind, vector<int>& v, bool buy,
vector<vector<int> >& memo)
{
// No prices left
if (ind >= v.size())
return 0;
// Already found
if (memo[ind][buy] != -1)
return memo[ind][buy];
// Already bought, now sell
if (buy) {
return memo[ind][buy]
= max(-v[ind] + find(ind + 1, v, !buy, memo),
find(ind + 1, v, buy, memo));
}
// Otherwise, buy the stock
else {
return memo[ind][buy]
= max(v[ind] + find(ind + 1, v, !buy, memo),
find(ind + 1, v, buy, memo));
}
}
// Function to find the maximum
// profit possible by buying and
// selling stocks any number of times
int maxProfit(vector<int>& prices)
{
int n = prices.size();
if (n < 2)
return 0;
vector<vector<int> > v(n + 1, vector<int>(2, -1));
return find(0, prices, 1, v);
}
// Driver Code
int main()
{
// Given prices
vector<int> prices = { 7, 1, 5, 3, 6, 4 };
// Function Call to calculate
// maximum profit possible
int ans = maxProfit(prices);
// Print the total profit
cout << ans << endl;
return 0;
}
Java
// Java code for the above approach
import java.util.*;
class GFG {
// Function to find maximum profit possible
// by buying and selling at most one stack
static int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp=new int[n][2];
for(int[] row:dp) Arrays.fill(row,-1);
return findMaximumProfit(0,1,prices,dp);
}
static int findMaximumProfit( int i, int k,
int[] prices, int[][] dp)
{
if(i == prices.length) return 0;
if(dp[i][k] != -1) return dp[i][k];
int profit = 0;
if(k == 1){
int buy = -prices[i] + findMaximumProfit(i+1,0,prices,dp);
int notBuy = findMaximumProfit(i+1,1,prices,dp);
profit = Math.max(buy,notBuy);
}else{
int sell = prices[i] + findMaximumProfit(i+1,1,prices,dp);
int notSell = findMaximumProfit(i+1,0,prices,dp);
profit = Math.max(sell, notSell);
}
return dp[i][k] = profit;
}
// Driver Code
public static void main(String[] args)
{
// Given prices
int[] prices = { 7, 1, 5, 3, 6, 4 };
int ans = maxProfit(prices);
// Print answer
System.out.println(ans);
}
}
7
Complejidad de tiempo: O(N) donde N es la longitud de la array dada.
Espacio Auxiliar: O(N)
Método 2: – Solución optimizada
Una forma más de resolver el problema es pensar en la situación en la que compramos las acciones al comienzo de la corriente ascendente en el gráfico de acciones y las vendemos en el punto más alto de esa línea ascendente del gráfico. Solo tenemos que calcular la suma de todas las corrientes ascendentes que están presentes en el gráfico.
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 the maximum profit possible by buying
// and selling stocks any number of times
int maxProfit(vector<int>& prices)
{
int n = prices.size();
if (n < 2)
return 0;
int sellingDate = 0;
int buyingDate = 0;
int totalProfit = 0;
for (int i = 1; i < prices.size(); i++) {
if (prices[i] >= prices[i - 1])
sellingDate++;
else {
totalProfit += (prices[sellingDate] - prices[buyingDate]);
sellingDate = buyingDate = i;
}
}
totalProfit += (prices[sellingDate] - prices[buyingDate]);
return totalProfit;
}
// Driver Code
int main()
{
// Given prices
vector<int> prices = { 7, 1, 5, 3, 6, 4 };
// Function Call to calculate maximum profit possible
int ans = maxProfit(prices);
// Print the total profit
cout << ans << endl;
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Complejidad de tiempo: O(N) donde N es la longitud de la array dada.
Espacio Auxiliar: O(1)
Tipo III: Se permiten como máximo dos transacciones
Problema: Dada una array precio[] de longitud N que denota los precios de las acciones en diferentes días. La tarea es encontrar el máximo beneficio posible para comprar y vender acciones en diferentes días utilizando transacciones en las que se permiten dos transacciones como máximo.
Nota: Las acciones deben comprarse antes de venderse.
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
Enfoque 1: El problema se puede resolver siguiendo el enfoque anterior. Ahora, si el número de transacciones es igual a 2, entonces la ganancia actual puede ser la respuesta deseada. Del mismo modo, pruebe todas las respuestas posibles memorízándolas en la tabla DP.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function to find the maximum
// profit in the buy and sell stock
int find(vector<int>& prices, int ind, bool buy, int c,
vector<vector<vector<int> > >& memo)
{
// If buy =1 means buy now
// else sell
if (ind >= prices.size() || c >= 2)
return 0;
if (memo[ind][buy] != -1)
return memo[ind][buy];
// Already bought, sell now
if (buy) {
return memo[ind][buy]
= max(-prices[ind]
+ find(prices, ind + 1, !buy, c,
memo),
find(prices, ind + 1, buy, c, memo));
}
// Can buy stocks
else {
return memo[ind][buy]
= max(prices[ind]
+ find(prices, ind + 1, !buy,
c + 1, memo),
find(prices, ind + 1, buy, c, memo));
}
}
// Function to find the maximum
// profit in the buy and sell stock
int maxProfit(vector<int>& prices)
{
// Here maximum two transaction are allowed
// Use 3-D vector because here
// three states are there: i,k,buy/sell
vector<vector<vector<int> > > memo(
prices.size(),
vector<vector<int> >(2, vector<int>(2, -1)));
// Answer
return find(prices, 0, 1, 0, memo);
}
// Driver Code
int main()
{
// Given prices
vector<int> prices = { 3, 3, 5, 0, 0, 3, 1, 4 };
// Function Call
int ans = maxProfit(prices);
// Answer
cout << ans << endl;
return 0;
}
6
Complejidad temporal: O(N), donde N es la longitud de la array dada.
Espacio Auxiliar: O(N)
Enfoque 2: espacio optimizado
- Tenemos 4 variables aquí t1Cost, t2Cost, t1Profit y t2Profit.
- Representan el costo mínimo en cada transacción y la ganancia máxima que podemos obtener de cada transacción t1Cost y t1Profit son muy fáciles de obtener.
- Tenemos que reinvertir las ganancias que obtenemos de la primera transacción. Los precios de la segunda acción menos la ganancia máxima que tenemos de la primera transacción es el costo mínimo de la segunda transacción.
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function to find the maximum
// profit in the buy and sell stock
int maxProfit(vector<int> prices) {
// O(n) time | O(1) space
if(prices.size() <= 1) return 0;
int t1Cost = INT_MAX, t2Cost = INT_MAX;
int t1Profit = 0, t2Profit = 0;
for(int price : prices)
{
// first transaction is as same as 121. Best Time to Buy and Sell Stock
t1Cost = min(t1Cost, price);
t1Profit = max(t1Profit, price - t1Cost);
// reinvest the gained profit in the second transaction
t2Cost = min(t2Cost, price - t1Profit);
t2Profit = max(t2Profit, price - t2Cost);
}
return t2Profit;
}
// Driver Code
int main()
{
// Given prices
vector<int> prices = { 3, 3, 5, 0, 0, 3, 1, 4 };
// Function Call
int ans = maxProfit(prices);
// Answer
cout << ans << endl;
return 0;
}
Complejidad temporal: O(N), donde N es la longitud de la array dada.
Espacio Auxiliar : O(1)
Tipo IV: Se permiten como máximo K transacciones
Problema: Dada una array precio[] de longitud N que denota los precios de las acciones en diferentes días. La tarea es encontrar el máximo beneficio posible para comprar y vender acciones en diferentes días utilizando transacciones en las que se permiten como máximo K transacciones.
Nota: Las acciones deben comprarse antes de venderse.
Ejemplos:
Entrada: K = 2, precios[] = {2, 4, 1}
Salida: 2
Explicación: compre el día 1 cuando el precio sea 2 y venda el día 2 cuando el precio sea 4. Por lo tanto, beneficio = 4-2 = 2.Entrada: K = 2, precios[] = {3, 2, 6, 5, 0, 3}
Salida: 7
Explicación:
Compre el día 2 cuando el precio sea 2 y venda el día 3 cuando el precio sea 6. Por lo tanto, beneficio = 6-2 = 4.
Compre el día 5 cuando el precio sea 0 y venda el día 6 cuando el precio sea 3. Por lo tanto, la ganancia = 3-0 = 3.
Por lo tanto, la ganancia total = 4+3 = 7
Enfoque: La idea es mantener el conteo de transacciones completadas hasta y comparar el conteo de la transacción con K . Si es menor que K , compre y venda las acciones. De lo contrario, el beneficio actual puede ser el beneficio máximo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function to find the maximum
// profit with atmost K transactions
int find(vector<int>& prices, int ind, bool buy, int c,
int k, vector<vector<vector<int> > >& memo)
{
// If there are no more transaction
// allowed, return the profit as 0
if (ind >= prices.size() || c >= k)
return 0;
// Memoize
else if (memo[ind][buy] != -1)
return memo[ind][buy];
// Already bought, now sell
if (buy) {
return memo[ind][buy] = max(
-prices[ind]
+ find(prices, ind + 1, !buy, c, k,
memo),
find(prices, ind + 1, buy, c, k, memo));
}
// Stocks can be bought
else {
return memo[ind][buy] = max(
prices[ind]
+ find(prices, ind + 1, !buy, c + 1,
k, memo),
find(prices, ind + 1, buy, c, k, memo));
}
}
// Function to find the maximum profit
// in the buy and sell stock
int maxProfit(int k, vector<int>& prices)
{
// If transactions are greater
// than number of prices
if (2 * k > prices.size()) {
int res = 0;
for (int i = 1; i < prices.size(); i++) {
res += max(0, prices[i] - prices[i - 1]);
}
return res;
}
// Maximum k transaction
vector<vector<vector<int> > > memo(
prices.size() + 1,
vector<vector<int> >(2, vector<int>(k + 1, -1)));
return find(prices, 0, 1, 0, k, memo);
}
// Driver Code
int main()
{
// Given prices
vector<int> prices = { 2, 4, 1 };
// Given K
int k = 2;
// Function Call
int ans = maxProfit(k, prices);
// Print answer
cout << ans << endl;
return 0;
}
2
Complejidad de tiempo: O(N*K), donde N es la longitud de la array dada y K es el número de transacciones permitidas.
Espacio Auxiliar: O(N*K)
Publicación traducida automáticamente
Artículo escrito por shubhagrawal1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA