El precio de una acción en cada día se da en una array arr[] para N días, la tarea es encontrar la ganancia máxima que se puede obtener comprando y vendiendo las acciones en esos días con las condiciones de que la acción debe venderse antes. comprar nuevamente y las acciones no se pueden comprar al día siguiente de vender una acción. (es decir, descansar al menos un día).
Ejemplos:
Entrada: arr[] = {2, 4, 5, 0, 2}
Salida: 4
Explicación: Compre a costo 2 y venda a costo 4, ganancia = 2. Compre a costo 0 y venda a costo 2, ganancia = 2. Beneficio total = 4.Entrada: arr[] = {2, 0, 5, 1, 8}
Salida: 8
Enfoque:
Considere tres estados: DESCANSO , ESPERA y VENDIDO .
DESCANSO significa no hacer nada.
HOLD significa mantener acciones (compró una acción y no la vendió).
VENDIDO significa estado después de vender las acciones.
Para alcanzar el estado REPOSO , no haga nada.
Para llegar al estado HOLD , compre las acciones.
Para llegar al estado VENDIDO , venda las acciones para las que primero hay necesidad de comprar.
Mediante las acciones anteriores, se realiza un diagrama de transición.
Mediante el uso de este diagrama de transición se puede averiguar el beneficio.
El día i :
- rest[i] denota el beneficio máximo obtenido al descansar en el día i. Dado que el i -ésimo día es día de descanso, es posible que las acciones se hayan vendido el (i-1) -ésimo día o que no se hayan vendido. El valor de resto[i] = max( resto[i-1], vendido[i-1]) .
- hold[i] denota el beneficio máximo obtenido al comprar el i -ésimo día o al comprar algún día antes del i -ésimo y descansar el i -ésimo día. Entonces, el valor de hold[i] = max( hold[i-1], rest[i-1]+price[i]) .
- sold[i] denota la ganancia máxima al vender el i -ésimo día. Las acciones deben haberse comprado algún día antes de venderlas el día i . Por lo tanto, vendido[i] = retener[i-1] + precio[i] .
Por lo tanto, la respuesta final será la
máximo de vendido[n-1] y resto[n-1] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above problem
#include <bits/stdc++.h>
using namespace std;
int maxProfit(int prices[], int n)
{
// If there is only one day
// for buying and selling
// no profit can be made
if (n <= 1)
return 0;
// Array to store Maxprofit by
// resting on given day
int rest[n] = { 0 };
// Array to store Maxprofit by
// buying or resting on the
// given day
int hold[n] = { 0 };
// Array to store Maxprofit by
// selling on given day
int sold[n] = { 0 };
// Initially there will 0 profit
rest[0] = 0;
// Buying on 1st day results
// in negative profit
hold[0] = -prices[0];
// zero profit since selling
// before buying isn't possible
sold[0] = 0;
for (int i = 1; i < n; i++) {
// max of profit on (i-1)th
// day by resting and profit
// on (i-1)th day by selling.
rest[i] = max(rest[i - 1],
sold[i - 1]);
// max of profit by resting
// on ith day and
// buying on ith day.
hold[i] = max(hold[i - 1],
rest[i - 1]
- prices[i]);
// max of profit by selling
// on ith day
sold[i] = hold[i - 1] + prices[i];
}
// maxprofit
return max(rest[n - 1],
sold[n - 1]);
}
// Driver Code
int main()
{
int price[] = { 2, 4,
5, 0, 2 };
int n = sizeof(price)
/ sizeof(price[0]);
cout << maxProfit(price, n)
<< endl;
return 0;
}
Java
// Java program for the above problem
class GFG{
static int maxProfit(int prices[], int n)
{
// If there is only one day
// for buying and selling
// no profit can be made
if (n <= 1)
return 0;
// Array to store Maxprofit by
// resting on given day
int rest[] = new int[n];
// Array to store Maxprofit by
// buying or resting on the
// given day
int hold[] = new int[9];
// Array to store Maxprofit by
// selling on given day
int sold[] = new int[9];
// Initially there will 0 profit
rest[0] = 0;
// Buying on 1st day results
// in negative profit
hold[0] = -prices[0];
// Zero profit since selling
// before buying isn't possible
sold[0] = 0;
for(int i = 1; i < n; i++)
{
// max of profit on (i-1)th
// day by resting and profit
// on (i-1)th day by selling.
rest[i] = Math.max(rest[i - 1],
sold[i - 1]);
// max of profit by resting
// on ith day and
// buying on ith day.
hold[i] = Math.max(hold[i - 1],
rest[i - 1] -
prices[i]);
// max of profit by selling
// on ith day
sold[i] = hold[i - 1] + prices[i];
}
// maxprofit
return Math.max(rest[n - 1],
sold[n - 1]);
}
// Driver Code
public static void main(String[] args)
{
int price[] = { 2, 4, 5, 0, 2 };
int n = price.length;
System.out.print(maxProfit(price, n) + "\n");
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 program for the above problem def maxProfit(prices, n): # If there is only one day # for buying and selling # no profit can be made if (n <= 1): return 0 # Array to store Maxprofit by # resting on given day rest = [0] * n # Array to store Maxprofit by # buying or resting on the # given day hold = [0] * n # Array to store Maxprofit by # selling on given day sold = [0] * n # Initially there will 0 profit rest[0] = 0 # Buying on 1st day results # in negative profit hold[0] = -prices[0] # zero profit since selling # before buying isn't possible sold[0] = 0 for i in range(1, n): # max of profit on (i-1)th # day by resting and profit # on (i-1)th day by selling. rest[i] = max(rest[i - 1], sold[i - 1]) # max of profit by resting # on ith day and # buying on ith day. hold[i] = max(hold[i - 1], rest[i - 1] - prices[i]) # max of profit by selling # on ith day sold[i] = hold[i - 1] + prices[i] # maxprofit return max(rest[n - 1], sold[n - 1]) # Driver Code price = [ 2, 4, 5, 0, 2 ] n = len(price) print(maxProfit(price, n)) # This code is contributed by avanitrachhadiya2155
C#
// C# program for the above problem
using System;
class GFG{
static int maxProfit(int[] prices, int n)
{
// If there is only one day
// for buying and selling
// no profit can be made
if (n <= 1)
return 0;
// Array to store Maxprofit by
// resting on given day
int[] rest = new int[n];
// Array to store Maxprofit by
// buying or resting on the
// given day
int[] hold = new int[9];
// Array to store Maxprofit by
// selling on given day
int[] sold = new int[9];
// Initially there will 0 profit
rest[0] = 0;
// Buying on 1st day results
// in negative profit
hold[0] = -prices[0];
// Zero profit since selling
// before buying isn't possible
sold[0] = 0;
for(int i = 1; i < n; i++)
{
// max of profit on (i-1)th
// day by resting and profit
// on (i-1)th day by selling.
rest[i] = Math.Max(rest[i - 1],
sold[i - 1]);
// max of profit by resting
// on ith day and
// buying on ith day.
hold[i] = Math.Max(hold[i - 1],
rest[i - 1] -
prices[i]);
// max of profit by selling
// on ith day
sold[i] = hold[i - 1] + prices[i];
}
// maxprofit
return Math.Max(rest[n - 1],
sold[n - 1]);
}
// Driver code
static void Main()
{
int[] price = { 2, 4, 5, 0, 2 };
int n = price.Length;
Console.WriteLine(maxProfit(price, n));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// JavaScript program for the above problem
function maxProfit( prices, n)
{
// If there is only one day
// for buying and selling
// no profit can be made
if (n <= 1)
return 0;
// Array to store Maxprofit by
// resting on given day
let rest = [];
for(let k = 0;k<n;k++)
rest.push(0);
// Array to store Maxprofit by
// buying or resting on the
// given day
let hold = [];
for(let k = 0;k<n;k++)
hold.push(0);
// Array to store Maxprofit by
// selling on given day
let sold = [];
for(let k = 0;k<n;k++)
sold.push(0);
// Initially there will 0 profit
rest[0] = 0;
// Buying on 1st day results
// in negative profit
hold[0] = -prices[0];
// zero profit since selling
// before buying isn't possible
sold[0] = 0;
for (let i = 1; i < n; i++) {
// max of profit on (i-1)th
// day by resting and profit
// on (i-1)th day by selling.
rest[i] = Math.max(rest[i - 1],
sold[i - 1]);
// max of profit by resting
// on ith day and
// buying on ith day.
hold[i] = Math.max(hold[i - 1],
rest[i - 1]
- prices[i]);
// max of profit by selling
// on ith day
sold[i] = hold[i - 1] + prices[i];
}
// maxprofit
return Math.max(rest[n - 1],
sold[n - 1]);
}
// Driver Code
let price = [ 2, 4,
5, 0, 2 ];
let n = price.length;
document.write( maxProfit(price, n),'<br>');
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)