En el comercio de acciones, un comprador compra acciones y las vende en una fecha futura. Dado el precio de las acciones de n días, el comerciante puede realizar como máximo k transacciones, donde una nueva transacción solo puede comenzar después de que se complete la transacción anterior, averigüe la ganancia máxima que podría haber obtenido un comerciante de acciones.
Ejemplos:
Input:
Price = [10, 22, 5, 75, 65, 80]
K = 2
Output: 87
Trader earns 87 as sum of 12 and 75
Buy at price 10, sell at 22, buy at
5 and sell at 80
Input:
Price = [12, 14, 17, 10, 14, 13, 12, 15]
K = 3
Output: 12
Trader earns 12 as the sum of 5, 4 and 3
Buy at price 12, sell at 17, buy at 10
and sell at 14 and buy at 12 and sell
at 15
Input:
Price = [100, 30, 15, 10, 8, 25, 80]
K = 3
Output: 72
Only one transaction. Buy at price 8
and sell at 80.
Input:
Price = [90, 80, 70, 60, 50]
K = 1
Output: 0
Not possible to earn.
Hay varias versiones del problema. Si se nos permite comprar y vender solo una vez, entonces podemos usar el algoritmo Diferencia máxima entre los dos elementos. Si se nos permite realizar como máximo 2 transacciones, podemos seguir el enfoque discutido aquí . Si se nos permite comprar y vender cualquier cantidad de veces, podemos seguir el enfoque discutido aquí .
Método 1 Programación Dinámica
En esta publicación, solo podemos realizar transacciones con un máximo de k. El problema se puede resolver usando programación dinámica.
Deje que profit[t][i] represente la ganancia máxima utilizando como máximo t transacciones hasta el día i (incluido el día i). Entonces la relación es:
beneficio[t][i] = max(beneficio[t][i-1], max(precio[i] – precio[j] + beneficio[t-1][j]))
para todos j en el rango [0, i-1] el
beneficio [t] [i] será el máximo de –
- profit[t][i-1] que representa no realizar ninguna transacción en el i-ésimo día.
- Beneficio máximo obtenido por la venta en el i-ésimo día. Para vender acciones en el i-ésimo día, necesitamos comprarlas en cualquiera de los [0, i – 1] días. Si compramos acciones el día j y las vendemos el día i, la ganancia máxima será precio[i] – precio[j] + ganancia[t-1][j] donde j varía de 0 a i-1. Aquí el beneficio[t-1][j] es lo mejor que podríamos haber hecho con una transacción menos hasta el día j.
A continuación se muestra la implementación basada en la programación dinámica.
C++
// C++ program to find out maximum profit by
// buying and selling a share atmost k times
// given stock price of n days
#include <climits>
#include <iostream>
using namespace std;
// Function to find out maximum profit by buying
// & selling a share atmost k times given stock
// price of n days
int maxProfit(int price[], int n, int k)
{
// table to store results of subproblems
// profit[t][i] stores maximum profit using
// atmost t transactions up to day i (including
// day i)
int profit[k + 1][n + 1];
// For day 0, you can't earn money
// irrespective of how many times you trade
for (int i = 0; i <= k; i++)
profit[i][0] = 0;
// profit is 0 if we don't do any transaction
// (i.e. k =0)
for (int j = 0; j <= n; j++)
profit[0][j] = 0;
// fill the table in bottom-up fashion
for (int i = 1; i <= k; i++) {
for (int j = 1; j < n; j++) {
int max_so_far = INT_MIN;
for (int m = 0; m < j; m++)
max_so_far = max(max_so_far,
price[j] - price[m] + profit[i - 1][m]);
profit[i][j] = max(profit[i][j - 1], max_so_far);
}
}
return profit[k][n - 1];
}
// Driver code
int main()
{
int k = 2;
int price[] = { 10, 22, 5, 75, 65, 80 };
int n = sizeof(price) / sizeof(price[0]);
cout << "Maximum profit is: "
<< maxProfit(price, n, k);
return 0;
}
Java
// Java program to find out maximum
// profit by buying and selling a
// share atmost k times given
// stock price of n days
class GFG {
// Function to find out
// maximum profit by
// buying & selling a
// share atmost k times
// given stock price of n days
static int maxProfit(int[] price,
int n,
int k)
{
// table to store results
// of subproblems
// profit[t][i] stores
// maximum profit using
// atmost t transactions up
// to day i (including day i)
int[][] profit = new int[k + 1][n + 1];
// For day 0, you can't
// earn money irrespective
// of how many times you trade
for (int i = 0; i <= k; i++)
profit[i][0] = 0;
// profit is 0 if we don't
// do any transaction
// (i.e. k =0)
for (int j = 0; j <= n; j++)
profit[0][j] = 0;
// fill the table in
// bottom-up fashion
for (int i = 1; i <= k; i++)
{
for (int j = 1; j < n; j++)
{
int max_so_far = 0;
for (int m = 0; m < j; m++)
max_so_far = Math.max(max_so_far, price[j] -
price[m] + profit[i - 1][m]);
profit[i][j] = Math.max(profit[i] [j - 1],
max_so_far);
}
}
return profit[k][n - 1];
}
// Driver code
public static void main(String []args)
{
int k = 2;
int[] price = { 10, 22, 5, 75, 65, 80 };
int n = price.length;
System.out.println("Maximum profit is: " +
maxProfit(price, n, k));
}
}
// This code is contributed by Anshul Aggarwal.
Python3
# Python program to maximize the profit
# by doing at most k transactions
# given stock prices for n days
# Function to find out maximum profit by
# buying & selling a share atmost k times
# given stock price of n days
def maxProfit(prices, n, k):
# Bottom-up DP approach
profit = [[0 for i in range(k + 1)]
for j in range(n)]
# Profit is zero for the first
# day and for zero transactions
for i in range(1, n):
for j in range(1, k + 1):
max_so_far = 0
for l in range(i):
max_so_far = max(max_so_far, prices[i] -
prices[l] + profit[l][j - 1])
profit[i][j] = max(profit[i - 1][j], max_so_far)
return profit[n - 1][k]
# Driver code
k = 2
prices = [10, 22, 5, 75, 65, 80]
n = len(prices)
print("Maximum profit is:",
maxProfit(prices, n, k))
# This code is contributed by vaibhav29498
C#
// C# program to find out maximum profit by
// buying and selling a share atmost k times
// given stock price of n days
using System;
class GFG {
// Function to find out maximum profit by
// buying & selling/ a share atmost k times
// given stock price of n days
static int maxProfit(int[] price, int n, int k)
{
// table to store results of subproblems
// profit[t][i] stores maximum profit using atmost
// t transactions up to day i (including day i)
int[, ] profit = new int[k + 1, n + 1];
// For day 0, you can't earn money
// irrespective of how many times you trade
for (int i = 0; i <= k; i++)
profit[i, 0] = 0;
// profit is 0 if we don't do any transaction
// (i.e. k =0)
for (int j = 0; j <= n; j++)
profit[0, j] = 0;
// fill the table in bottom-up fashion
for (int i = 1; i <= k; i++) {
for (int j = 1; j < n; j++) {
int max_so_far = 0;
for (int m = 0; m < j; m++)
max_so_far = Math.Max(max_so_far, price[j] -
price[m] + profit[i - 1, m]);
profit[i, j] = Math.Max(profit[i, j - 1], max_so_far);
}
}
return profit[k, n - 1];
}
// Driver code to test above
public static void Main()
{
int k = 2;
int[] price = { 10, 22, 5, 75, 65, 80 };
int n = price.Length;
Console.Write("Maximum profit is: " +
maxProfit(price, n, k));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to find out maximum profit by
// buying and selling a share atmost k times
// given stock price of n days
// Function to find out maximum profit by buying
// & selling a share atmost k times given stock
// price of n days
function maxProfit($price, $n, $k)
{
// table to store results of subproblems
// profit[t][i] stores maximum profit using
// atmost t transactions up to day i (including
// day i)
$profit[$k + 1][$n + 1] = 0;
// For day 0, you can't earn money
// irrespective of how many times you trade
for ($i = 0; $i <= $k; $i++)
$profit[$i][0] = 0;
// profit is 0 if we don't
// do any transaction
// (i.e. k =0)
for ($j = 0; $j <= $n; $j++)
$profit[0][$j] = 0;
// fill the table in
// bottom-up fashion
for ($i = 1; $i <= $k; $i++) {
for ($j = 1; $j < $n; $j++) {
$max_so_far = PHP_INT_MIN;
for ($m = 0; $m < $j; $m++)
$max_so_far = max($max_so_far,
$price[$j] - $price[$m] +
$profit[$i - 1][$m]);
$profit[$i][$j] = max($profit[$i][$j - 1],
$max_so_far);
}
}
return $profit[$k][$n - 1];
}
// Driver code
$k = 2;
$price = array (10, 22, 5, 75, 65, 80 );
$n = sizeof($price);
echo "Maximum profit is: ". maxProfit($price, $n, $k);
// This is contributed by mits
?>
Javascript
<script>
// javascript program to find out maximum
// profit by buying and selling a
// share atmost k times given
// stock price of n days
// Function to find out
// maximum profit by
// buying & selling a
// share atmost k times
// given stock price of n days
function maxProfit(price,n, k)
{
// table to store results
// of subproblems
// profit[t][i] stores
// maximum profit using
// atmost t transactions up
// to day i (including day i)
var profit = Array(k+1).fill(0).map
(x => Array(n+1).fill(0));
// For day 0, you can't
// earn money irrespective
// of how many times you trade
for (i = 0; i <= k; i++)
profit[i][0] = 0;
// profit is 0 if we don't
// do any transaction
// (i.e. k =0)
for (j = 0; j <= n; j++)
profit[0][j] = 0;
// fill the table in
// bottom-up fashion
for (i = 1; i <= k; i++)
{
for (j = 1; j < n; j++)
{
var max_so_far = 0;
for (m = 0; m < j; m++)
max_so_far = Math.max(max_so_far, price[j] -
price[m] + profit[i - 1][m]);
profit[i][j] = Math.max(profit[i] [j - 1],
max_so_far);
}
}
return profit[k][n - 1];
}
// Driver code
var k = 2;
var price = [ 10, 22, 5, 75, 65, 80 ];
var n = price.length;
document.write("Maximum profit is: " +
maxProfit(price, n, k));
// This code contributed by shikhasingrajput
</script>
Producción :
Maximum profit is: 87
La solución anterior tiene una complejidad temporal de O(kn 2 ). Se puede reducir si somos capaces de calcular la ganancia máxima obtenida por la venta de acciones en el i-ésimo día en tiempo constante.
beneficio[t][i] = max(beneficio [t][i-1], max(precio[i] – precio[j] + beneficio[t-1][j]))
para todos los j en el rango [0 , i-1]
Si observamos cuidadosamente,
max(price[i] – price[j] + profit[t-1][j])
para todos los j en el rango [0, i-1]
se puede reescribir como,
= precio[i] + max(beneficio[t-1][j] – precio[j])
para todos los j en el rango [0, i-1]
= precio[i] + max(prevDiff, beneficio[t-1] [i-1] – precio[i-1])
donde prevDiff es max(beneficio[t-1][j] – precio[j])
para todos los j en el rango [0, i-2]
Entonces, si ya calculamos max(beneficio[t-1][j] – precio[j]) para todos los j en el rango [0, i-2], podemos calcularlo para j = i – 1 en tiempo constante . En otras palabras, ya no tenemos que mirar hacia atrás en el rango [0, i-1] para encontrar el mejor día para comprar. Podemos determinar eso en tiempo constante usando la siguiente relación revisada.
beneficio[t][i] = max(beneficio[t][i-1], precio[i] + max(prevDiff, beneficio [t-1][i-1] – precio[i-1])
donde prevDiff es max(beneficio[t-1][j] – precio[j]) para todos los j en el rango [0, i-2]
A continuación se muestra su implementación optimizada:
C++
// C++ program to find out maximum profit by buying
// and/ selling a share atmost k times given stock
// price of n days
#include <climits>
#include <iostream>
using namespace std;
// Function to find out maximum profit by buying &
// selling/ a share atmost k times given stock price
// of n days
int maxProfit(int price[], int n, int k)
{
// table to store results of subproblems
// profit[t][i] stores maximum profit using atmost
// t transactions up to day i (including day i)
int profit[k + 1][n + 1];
// For day 0, you can't earn money
// irrespective of how many times you trade
for (int i = 0; i <= k; i++)
profit[i][0] = 0;
// profit is 0 if we don't do any transaction
// (i.e. k =0)
for (int j = 0; j <= n; j++)
profit[0][j] = 0;
// fill the table in bottom-up fashion
for (int i = 1; i <= k; i++) {
int prevDiff = INT_MIN;
for (int j = 1; j < n; j++) {
prevDiff = max(prevDiff,
profit[i - 1][j - 1] - price[j - 1]);
profit[i][j] = max(profit[i][j - 1],
price[j] + prevDiff);
}
}
return profit[k][n - 1];
}
// Driver Code
int main()
{
int k = 3;
int price[] = { 12, 14, 17, 10, 14, 13, 12, 15 };
int n = sizeof(price) / sizeof(price[0]);
cout << "Maximum profit is: "
<< maxProfit(price, n, k);
return 0;
}
Java
// Java program to find out maximum
// profit by buying and selling a
// share atmost k times given stock
// price of n days
import java.io.*;
class GFG {
// Function to find out maximum profit by
// buying & selling/ a share atmost k times
// given stock price of n days
static int maxProfit(int price[],
int n, int k)
{
// table to store results of subproblems
// profit[t][i] stores maximum profit
// using atmost t transactions up to day
// i (including day i)
int profit[][] = new int[k + 1][ n + 1];
// For day 0, you can't earn money
// irrespective of how many times you trade
for (int i = 0; i <= k; i++)
profit[i][0] = 0;
// profit is 0 if we don't do any
// transaction (i.e. k =0)
for (int j = 0; j <= n; j++)
profit[0][j] = 0;
// fill the table in bottom-up fashion
for (int i = 1; i <= k; i++)
{
int prevDiff = Integer.MIN_VALUE;
for (int j = 1; j < n; j++)
{
prevDiff = Math.max(prevDiff,
profit[i - 1][j - 1] -
price[j - 1]);
profit[i][j] = Math.max(profit[i][j - 1],
price[j] + prevDiff);
}
}
return profit[k][n - 1];
}
// Driver code
public static void main (String[] args)
{
int k = 3;
int price[] = {12, 14, 17, 10, 14, 13, 12, 15};
int n = price.length;
System.out.println("Maximum profit is: " +
maxProfit(price, n, k));
}
}
// This code is contributed by Sam007
Python3
# Python3 program to find out maximum
# profit by buying and/ selling a share
# at most k times given the stock price
# of n days
# Function to find out maximum profit
# by buying & selling/ a share atmost
# k times given stock price of n days
def maxProfit(price, n, k):
# Table to store results of subproblems
# profit[t][i] stores maximum profit
# using atmost t transactions up to
# day i (including day i)
profit = [[0 for i in range(n + 1)]
for j in range(k + 1)]
# Fill the table in bottom-up fashion
for i in range(1, k + 1):
prevDiff = float('-inf')
for j in range(1, n):
prevDiff = max(prevDiff,
profit[i - 1][j - 1] -
price[j - 1])
profit[i][j] = max(profit[i][j - 1],
price[j] + prevDiff)
return profit[k][n - 1]
# Driver Code
if __name__ == "__main__":
k = 3
price = [12, 14, 17, 10, 14, 13, 12, 15]
n = len(price)
print("Maximum profit is:",
maxProfit(price, n, k))
# This code is contributed
# by Rituraj Jain
C#
// C# program to find out maximum profit by buying
// and selling a share atmost k times given stock
// price of n days
using System;
class GFG {
// Function to find out maximum profit by
// buying & selling/ a share atmost k times
// given stock price of n days
static int maxProfit(int[] price, int n, int k)
{
// table to store results of subproblems
// profit[t][i] stores maximum profit using atmost
// t transactions up to day i (including day i)
int[, ] profit = new int[k + 1, n + 1];
// For day 0, you can't earn money
// irrespective of how many times you trade
for (int i = 0; i <= k; i++)
profit[i, 0] = 0;
// profit is 0 if we don't do any transaction
// (i.e. k =0)
for (int j = 0; j <= n; j++)
profit[0, j] = 0;
// fill the table in bottom-up fashion
for (int i = 1; i <= k; i++) {
int prevDiff = int.MinValue;
for (int j = 1; j < n; j++) {
prevDiff = Math.Max(prevDiff,
profit[i - 1, j - 1] - price[j - 1]);
profit[i, j] = Math.Max(profit[i, j - 1],
price[j] + prevDiff);
}
}
return profit[k, n - 1];
}
// Driver code to test above
public static void Main()
{
int k = 3;
int[] price = {12, 14, 17, 10, 14, 13, 12, 15};
int n = price.Length;
Console.Write("Maximum profit is: " +
maxProfit(price, n, k));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to find out maximum
// profit by buying and selling a
// share atmost k times given stock
// price of n days
// Function to find out maximum
// profit by buying & selling a
// share atmost k times given
// stock price of n days
function maxProfit($price, $n, $k)
{
// table to store results
// of subproblems profit[t][i]
// stores maximum profit using
// atmost t transactions up to
// day i (including day i)
$profit[$k + 1][$n + 1]=0;
// For day 0, you can't
// earn money irrespective
// of how many times you trade
for ($i = 0; $i <= $k; $i++)
$profit[$i][0] = 0;
// profit is 0 if we don't
// do any transaction
// (i.e. k =0)
for ($j = 0; $j <= $n; $j++)
$profit[0][$j] = 0;
// fill the table in
// bottom-up fashion
$prevDiff = NULL;
for ($i = 1; $i <= $k; $i++) {
for ($j = 1; $j < $n; $j++) {
$prevDiff = max($prevDiff, $profit[$i - 1][$j - 1] -
$price[$j - 1]);
$profit[$i][$j] = max($profit[$i][$j - 1],
$price[$j] + $prevDiff);
}
}
return $profit[$k][$n - 1];
}
// Driver Code
$k = 3;
$price = array(12, 14, 17, 10,
14, 13, 12, 15);
$n = sizeof($price);
echo "Maximum profit is: "
, maxProfit($price, $n, $k);
// This code is contributed by nitin mittal
?>
Javascript
<script>
// javascript program to find out maximum
// profit by buying and selling a
// share atmost k times given stock
// price of n days
// Function to find out maximum profit by
// buying & selling/ a share atmost k times
// given stock price of n days
function maxProfit(price, n , k)
{
// table to store results of subproblems
// profit[t][i] stores maximum profit
// using atmost t transactions up to day
// i (including day i)
var profit = Array(k+1).fill(0).map(x => Array(n+1).fill(0));
// For day 0, you can't earn money
// irrespective of how many times you trade
for (var i = 0; i <= k; i++)
profit[i][0] = 0;
// profit is 0 if we don't do any
// transaction (i.e. k =0)
for (j = 0; j <= n; j++)
profit[0][j] = 0;
// fill the table in bottom-up fashion
for (var i = 1; i <= k; i++)
{
var prevDiff = -Number.MAX_VALUE;
for (var j = 1; j < n; j++)
{
prevDiff = Math.max(prevDiff,
profit[i - 1][j - 1] -
price[j - 1]);
profit[i][j] = Math.max(profit[i][j - 1],
price[j] + prevDiff);
}
}
return profit[k][n - 1];
}
// Driver code
var k = 3;
var price = [12, 14, 17, 10, 14, 13, 12, 15];
var n = price.length;
document.write("Maximum profit is: " +
maxProfit(price, n, k));
// This code contributed by shikhasingrajput
</script>
Producción :
Maximum profit is: 12
La complejidad temporal de la solución anterior es O(kn) y la complejidad espacial es O(nk). La complejidad del espacio se puede reducir aún más a O(n) cuando usamos el resultado de la última transacción. Pero para que el artículo sea fácilmente legible, hemos utilizado el espacio O(kn).
Este artículo es una contribución de Aditya Goel .
Método-2 Memoización (programación dinámica)
Otra forma de abordar este problema es considerar la compra y la venta como dos estados diferentes de la dp. Entonces consideraremos el dp de la siguiente manera:
Sea i el índice de la acción en la que estamos, j la transacción total restante, b represente si tenemos que vender o comprar esta acción (1 para comprar y 0 para vender) y A representar la array que contiene los precios de las acciones y luego indicar las transiciones será como sigue:
dp[i][j][1]=máx(-A[i]+dp[j][i+1][0],dp[j][i+1][1])
dp[i][j][0]=máx(A[i]+dp[j-1][i+1][1],dp[j][i+1][0])
implementación es la siguiente:
C++
// C++ program to find out maximum profit by
// buying and selling a share atmost k times
// given stock price of n days
#include <bits/stdc++.h>
using namespace std;
int B;
vector<int> A;
int dp[501][201][2];
int solve(int j, int i, int b)
{
// if the result has already been calculated return that result
if (dp[i][j][b] != -1)
return dp[i][j][b];
// if i has reached the end of the array return 0
if (i == B)
return 0;
// if we have exhausted the number of transaction return 0
if (j == 0)
return 0;
int res;
// if we are to buy stocks
if (b == 1)
res = max(-A[i] + solve(j, i + 1, 0), solve(j, i + 1, 1));
// if we are to sell stock and complete onr transaction
else
res = max(A[i] + solve(j - 1, i + 1, 1), solve(j, i + 1, 0));
// return the result
return dp[i][j][b] = res;
}
int maxProfit(int K, int N, int C[])
{
A = vector<int>(N, 0);
// Copying C to global A
for (int i = 0; i < N; i++)
A[i] = C[i];
// Initializing DP with -1
for (int i = 0; i <= N; i++)
for (int j = 0; j <= K; j++)
{
dp[i][j][1] = -1;
dp[i][j][0] = -1;
}
// Copying n to global B
B = N;
return solve(K, 0, 1);
}
// driver code
int main()
{
// TEST 1
int k1 = 3;
int price1[] = {12, 14, 17, 10, 14, 13, 12, 15};
int n1 = sizeof(price1) / sizeof(price1[0]);
cout << "Maximum profit is: "
<< maxProfit(k1, n1, price1) << endl;
// TEST 2
int k2 = 2;
int price2[] = {10, 22, 5, 75, 65, 80};
int n2 = sizeof(price2) / sizeof(price2[0]);
cout << "Maximum profit is: "
<< maxProfit(k2, n2, price2);
return 0;
}
//This code is contributed by Anirudh Singh
Javascript
// JavaScript program to find out maximum profit by
// buying and selling a share atmost k times
// given stock price of n days
let B;
let A = [];
let dp = new Array(501);
for (let i = 0; i < 501; i++)
{
dp[i] = new Array(201);
for (let j = 0; j < 201; j++)
dp[i][j] = new Array(2);
}
function solve(j, i, b)
{
// if the result has already been calculated return that result
if (dp[i][j][b] != -1)
return dp[i][j][b];
// if i has reached the end of the array return 0
if (i == B)
return 0;
// if we have exhausted the number of transaction return 0
if (j == 0)
return 0;
let res;
// if we are to buy stocks
if (b == 1)
res = Math.max(-A[i] + solve(j, i + 1, 0), solve(j, i + 1, 1));
// if we are to sell stock and complete onr transaction
else
res = Math.max(A[i] + solve(j - 1, i + 1, 1), solve(j, i + 1, 0));
// return the result
return dp[i][j][b] = res;
}
function maxProfit(K, N, C)
{
A = new Array(N).fill(0);
// Copying C to global A
for (i = 0; i < N; i++)
A[i] = C[i];
// Initializing DP with -1
for (i = 0; i <= N; i++)
for (j = 0; j <= K; j++)
{
dp[i][j][1] = -1;
dp[i][j][0] = -1;
}
// Copying n to global B
B = N;
return solve(K, 0, 1);
}
// driver code
// TEST 1
let k1 = 3;
let price1 = [12, 14, 17, 10, 14, 13, 12, 15];
let n1 = price1.length;
console.log("Maximum profit is: " + maxProfit(k1, n1, price1));
// TEST 2
let k2 = 2;
let price2 = [10, 22, 5, 75, 65, 80];
let n2 = price2.length;
console.log("Maximum profit is: " + maxProfit(k2, n2, price2));
//This code is contributed by phasing17
Python3
# Python3 program to find out maximum profit by
# buying and selling a share atmost k times
# given stock price of n days
A = []
dp = [None for _ in range(501)]
for i in range(501):
dp[i] = [None for _ in range(201)]
for j in range(201):
dp[i][j] = [-1, -1]
B = len(dp)
def solve(j, i, b):
global dp, B
# if the result has already been calculated return that result
if (dp[i][j][b] != -1):
return dp[i][j][b]
# if i has reached the end of the array return 0
if (i == B):
return 0
# if we have exhausted the number of transaction return 0
if (j == 0):
return 0
# if we are to buy stocks
if (b == 1):
res = max(-A[i] + solve(j, i + 1, 0), solve(j, i + 1, 1))
# if we are to sell stock and complete onr transaction
else:
res = max(A[i] + solve(j - 1, i + 1, 1), solve(j, i + 1, 0))
# return the result
dp[i][j][b] = res
return res
def maxProfit(K, N, C):
global dp, B, A
A = [0 for _ in range(N)]
# Copying C to global A
A = C.copy()
# Initializing DP with -1
for i in range(N + 1):
for j in range(K + 1):
dp[i][j][1] = -1
dp[i][j][0] = -1
# Copying n to global B
B = N
return solve(K, 0, 1)
# Driver code
# TEST 1
k1 = 3
price1 = [12, 14, 17, 10, 14, 13, 12, 15]
n1 = len(price1)
print("Maximum profit is:", maxProfit(k1, n1, price1))
# TEST 2
k2 = 2
price2 = [10, 22, 5, 75, 65, 80]
n2 = len(price2)
print("Maximum profit is:", maxProfit(k2, n2, price2))
# This code is contributed by phasing17
Producción
Maximum profit is: 12 Maximum profit is: 87
Complejidad de tiempo: O(n*k)
Espacio Auxiliar: O(n*k)
Este enfoque e implementación es aportado por Anirudh Singh .
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA