Solve the Best Time to Buy and Sell Stock Problem
1. Problem Statement
You are given an integer array of prices where prices[i] is the price of a given stock on an ith day. Design an algorithm to find the maximum profit.
Some constraints are as follows:
- You may complete at most k transactions.
- You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.Example 2:
Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.2. Solution
The problem is to find out the maximum profit you can get for a stock during a certain period of time.
States
We have 2 states for a stock on a Day(i):
Buy:
* Last transaction action on the stock was a buy.
* This initiates a transaction and bumps the transaction count.Sell:
* Last transaction action on the stock was a sell.
* This closes the transaction.
Actions
Hence, there are 3 possible actions you can take on Day(i):
Action 1. Buy the stock, if there is no Buy done on an earlier day.
Action 2. Sell the stock, if there is a Buy done on an earlier day.
Action 3. Do Nothing.
States & Actions
Let’s rearrange the above into actions and states.
The goal is to calculate the max profit while making sure that the state (buy or sell) stays on that day and there is no transaction overlap.
Day(i) | Buy:
* Action 1: Do nothing = keep profit from Buy state on Day(i-1)
OR
* Action 2: Buy stock with profit from Sell state on Day(i-1)
[ensure that previous transaction is closed before initiating another one]Day(i) | Sell:
* Action 1: Do nothing = keep profit from Sell state on Day(i-1)
OR
* Action 2: Sell stock and add to profit from Buy state on Day(i-1)
[sell what was bought earlier]
States & Actions & Transactions
Now let’s add the transaction count constraint.
The goal is to calculate the max profit while making sure that the state (buy or sell) stays on that day, there is no transaction overlap and the transaction count is within limits.
Day(i) | Transaction(t) | Buy:
* Action 1: Do nothing = keep profit from Buy state on Day(i-1) & Transaction(t)
OR
* Action 2: Buy stock with profit from Sell state on Day(i-1) &
Transaction(t-1)
[ensure that previous transaction is closed before initiating another one and doing a buy will initiate a transaction leading to a bump so use t-1]Day(i) | Transaction(t) | Sell:
* Action 1: Do nothing = keep profit from Sell state on Day(i-1) & Transaction(t)
OR
* Action 2: Sell stock and add to profit from Buy state on Day(i-1) & Transaction(t)
[sell what was bought earlier]
If we calculate the above states for all days and transaction counts, we will eventually find out the maximum profit on the last day with the Sell state. Sell should be the last state since we want a transaction that’s closed towards the end since a Buy at the end would be a wasteful loss of money.
Time & Space Complexity
- Time Complexity: O(n * k) where n is the max number of days and k is the max transactions allowed. This is because we have to calculate profits for 2 states for all possible combinations of days and transaction counts.
- Space Complexity: O(k) where k is the max transactions allowed.
3. Optimization
The above O(n * k) solution works very well if k less than the maximum number of transactions possible.
But what if the transaction count was unlimited or in other words greater than the maximum number of mutually-exclusive transactions possible during those days? Can we do better?
A simpler solution for this case is to iterate through the days and start a transaction each time we see a local valley and sell on the local peak.
4. Code (Java)
The following code implements the logic explained above in Java.
Buy state is represented with a 1 and Sell state with 0.
public int maxProfit(int k, int[] prices) {
int days = prices.length;
if (days<=0 || k<= 0) {
return 0;
}
// If transactions allowed are max possible ...
if (k >= (days/2)) {
int maxProfit = 0;
int min = prices[0];
for (int i=1; i<days; i++) {
if (prices[i] < min) {
min = prices[i];
} else {
maxProfit += (prices[i] — min);
min = prices[i];
}
}
return maxProfit;
} // Find max profit for additional day with 0-k transactions.
int dp[][] = new int[k+1][2];
// Assigning negative values for cases which are not applicable.
for (int t = 0; t <= k; t++) {
dp[t][0] = -10000;
dp[t][1] = -10000;
}
dp[0][0] = 0;
dp[1][1] = -prices[0];
for (int d=1; d<days; d++) {
int dpNew[][] = dp.clone();
for (int t=0; t<=k; t++) {
dpNew[t][0] = Math.max(dp[t][0], dp[t][1] + prices[d]);
if (t==0) {
continue;
}
dpNew[t][1] = Math.max(dp[t][1], dp[t-1][0] — prices[d]);
}
}
// Find the max profit for the last day.
int maxProfit = 0;
for (int t=0; t<=k; t++) {
maxProfit = Math.max(maxProfit, dp[t][0]);
}
return maxProfit;
}
If you found this article useful, please help me reach more dev learners!
Show some ❤ by giving “claps” 👏 at the left margin of the page (on desktop) or at the bottom (on mobile). You can do so up to 50 times by clicking continuously!
Anum Malik
Follow NMTechBytes on Twitter for my daily tech bites :)
