Problem: Say you have an array for which the i-th element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most k transactions. Please note that you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Example:
Input: [2,1,2,0,1], k = 2 Output: 2 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 2), profit = 2-1 = 1. Then buy on day 4 (price = 0) and sell on day 5 (price = 1), profit = 1-0 = 1. so total profit is 1 + 1 = 2.
Approach: Like previous buy and sell stock problems, we are going to use DP here too. Lets take a 2D Table where Table[i][j] will tell the maximum profit on jth day by doing at most i sales. Obviously Table[k][n - 1] where n is size of array will be our answer. Here is how we are going to fill our table:
- Table[i][0] = 0 for all i = 0 to k as on day 0, profit will be 0 as no sale can be performed.
- Table[0][i] = 0 for all i = 0 to n - 1 as no sales have been performed so profit will be 0.
- Table [i][j] = MAX (Table[i][j -1], Max(prices[j] - prices[d] + Table[i - 1][d]) for all d = 0 to j - 1)
Let me explain point 3 in detail; At each day we have 2 choices -
- Do not sell the stock: Table[i][j] = Table[i][j - 1], the profit will remain same as the previous day with same number of sales.
- Sell the stock: In that case we need to see with each and every day's (before j) price and profit with 1 less sale:
- prices[j] - prices[d] to get the current profit
- Table[i - 1][d] to get the maximum profit till day d with i - 1 sales.
- So now you can see we need to get the maximum of prices[j] - prices[d] + Table[i - 1][d] for all d = 0 to j - 1.
That's it. This will solve our problem in O(k * n ^ 2) which is good but we can still do better. Let's see how:
Table[i][j] = MAX (Table[i][j -1], Max(prices[j] - prices[d] + Table[i - 1][d]) for all d = 0 to j - 1)
Max(prices[j] - prices[d] + Table[i - 1][d]) for all d = 0 to j - 1
= prices[j] + Max(Table[i-1][d] - prices[d]) for all d = 0 to j - 1
= prices[j] + Max(PrevMax, Table[i - 1][j - 1] - prices[j - 1])
Here PrevMax is Max(Table[i - 1][d] - prices[d]) for all d = 0 to j - 2. so now we can say:
Table[i][j] = MAX (Table[i][j -1], prices[j] + Max(PrevMax, Table[i - 1][j - 1] - prices[j - 1]))
The only problem is how we calculate the PrevMax in constant time or I would say how to have it calculated already for d = 0 to j - 2 so that we don't have to look back always. If you look at the implementation below then you will understand that for every i transaction we can calculate the PrevMax for all days (0....n) in the same loop to get the profit with i - 1 transactions.
Implementation in C#:
public static int MaxProfit(int k, int[] prices)
{
if (prices?.Length <= 1 || k <= 0)
{
return 0;
}
int result = 0;
if (k > prices.Length / 2) // special condition, we can do transactions as many as we want.
{
for(int i = 1; i < prices.Length; ++i)
{
result += Math.Max(0, prices[i] - prices[i - 1]);
}
return result;
}
int[,] table = new int[k + 1, prices.Length];
for (int i = 0; i <= k; ++i)
{
table[i, 0] = 0;
}
for (int i = 0; i < prices.Length; ++i)
{
table[0, i] = 0;
}
for (int i = 1; i <= k; ++i)
{
int prevMax = int.MinValue;
for (int j = 1; j < prices.Length; ++j)
{
prevMax = Math.Max(prevMax, table[i - 1, j - 1] - prices[j - 1]);
table[i, j] = Math.Max(table[i, j - 1], prices[j] + prevMax);
}
}
return table[k, prices.Length - 1];
}
Complexity: O(k * n)
Another approach: We can think of solution in another way too. Just a different perspective. We can have a 3D Table where Table[i][j][h] will tell the maximum profit on ith day with j buying transactions and h here could be 0 or 1 which will tell whether we are holding stocks or not. Finally max of Table[n-1][j][0] where j = 0 to k will be our answer. That is profit at the last day with at most k (j = 0 to k) sales without holding stock will be our answer. Here is how we fill the Table:
- Table[0][0][0] = 0
- Table[0][1][1] = -prices[0]; // Hold the stock means we purchase (1 transaction) the stock
- Now at every day, we can take following four actions:
- Keep holding the stock: Table[i][j][1] = Table[i - 1][j][1] // No change from last day to current day
- Keep not holding the stock: Table[i][j][0] = Table[i - 1][j][0] // No change from last day to current day
- Buy the stock: Table[i][j][1] = Table[i - 1][j - 1][0] - prices[i] // Now we will hold the stock h = 0, we go to previous day's max profit with one less buying transactions without holding stocks and subtract the current day's stock price (buy the stock)
- Sell the stock: Table[i][j][0] = Table[i-1][j][1] + prices[i] // Now we will hold the stock h = 1, we go ot previous day's max profit with same number of buying transactions but with holding the stock (as we need to sell) and add the current day's stock price as we are selling it.
- Now if you see, we can combine the above four points into 2:
- Table[i][j][0] = max (Table[i-1][j][0], Table[i-1][j][1] + prices[i])
- Table[i][j][1] = max (Table[i-1][j][1], Table[i-1][j-1][0] - prices[i])
That's it.
Implementation in C#:
public static int MaxProfit(int k, int[] prices)
{
if (prices?.Length <= 1 || k <= 0)
{
return 0;
}
int result = 0;
if (k > prices.Length)
{
for(int i = 1; i < prices.Length; ++i)
{
result += Math.Max(0, prices[i] - prices[i - 1]);
}
return result;
}
int[,,] table = new int[prices.Length, k + 1, 2];
for (int i = 0; i < prices.Length; ++i)
{
for (int j = 0; j <= k; ++j)
{
table[i, j, 0] = -1000000000; // int.Min can result into integer overflow
table[i, j, 1] = -1000000000;
}
}
table[0, 0, 0] = 0;
table[0, 1, 1] = -prices[0];
for (int i = 1; i < prices.Length; ++i)
{
for (int j = 0; j <= k; ++j)
{
table[i, j, 0] = Math.Max(table[i - 1, j, 0], table[i - 1, j, 1] + prices[i]);
if (j > 0)
{
table[i, j, 1] = Math.Max(table[i - 1, j, 1], table[i - 1, j - 1, 0] - prices[i]);
}
}
}
for (int i = 0; i <= k; ++i)
{
result = Math.Max(result, table[prices.Length - 1, i, 0]);
}
return result;
}
Complexity: O(n * k)
No comments:
Post a Comment