Leetcode 123. Best Time to Buy and Sell Stock III
Problem Explanation
In this problem, we are given price history of a given stock as an array, and we are asked to design an algorithm to maximize the profit by doing at most two transactions. A transaction here refers to buying and selling of stock. We can only sell the stock before we buy again.
Let's consider an example. If the input array of prices is [1,2,4,2,5,7,2,4,9,0], the maximum profit would be 13. We can buy a stock on day 1 at the price of 1 and sell it on day 6 at the price of 7, thus earning 6. Then we can buy another stock on day 7 at the price of 2 and sell it on day 9 at the price of 9, earning another 7. Total profit would be 6 + 7 = 13.
Approach
The solution uses dynamic programming to solve this problem. This problem is an example of the local-global DP problem. Here, there could be four possible states:
sellTwo
which represents the maximum profit after selling the stock for the second time.holdTwo
which represents the maximum profit after holding the stock for the second time.sellOne
which represents the maximum profit after selling the stock for the first time.holdOne
which represents the maximum profit after buying the stock for the first time.
We iterate over the prices and update these four states. sellOne
gets updated by the maximum value between sellOne
and the holdOne + price
. Similarly holdOne
gets updated by the maximum value between the previously stored holdOne
and -price
because we spent some cost price
to buy stock.
At the end the maximum profit would be stored in sellTwo
, we return that as result.
C++ Solution
1 2cpp 3class Solution { 4public: 5 int maxProfit(vector<int>& prices) { 6 int sellTwo = 0; 7 int holdTwo = INT_MIN; 8 int sellOne = 0; 9 int holdOne = INT_MIN; 10 11 for (const int price : prices) { 12 sellTwo = max(sellTwo, holdTwo + price); // sell the second stock 13 holdTwo = max(holdTwo, sellOne - price); // buy the second stock 14 sellOne = max(sellOne, holdOne + price); // sell the first stock 15 holdOne = max(holdOne, -price); // buy the first stock 16 } 17 18 return sellTwo; 19 } 20};
Python Solution
1 2python 3class Solution: 4 def maxProfit(self, prices): 5 sellTwo, holdTwo, sellOne, holdOne = 0, float('-inf'), 0, float('-inf') 6 for price in prices: 7 sellTwo = max(sellTwo, holdTwo + price) 8 holdTwo = max(holdTwo, sellOne - price) 9 sellOne = max(sellOne, holdOne + price) 10 holdOne = max(holdOne, -price) 11 return sellTwo
Java Solution
1 2java 3public class Solution { 4 public int maxProfit(int[] prices) { 5 int sellTwo = 0; 6 int holdTwo = Integer.MIN_VALUE; 7 int sellOne = 0; 8 int holdOne = Integer.MIN_VALUE; 9 10 for (int price : prices) { 11 sellTwo = Math.max(sellTwo, holdTwo + price); 12 holdTwo = Math.max(holdTwo, sellOne - price); 13 sellOne = Math.max(sellOne, holdOne + price); 14 holdOne = Math.max(holdOne, -price); 15 } 16 17 return sellTwo; 18 } 19}
JavaScript Solution
1 2javascript 3var maxProfit = function(prices) { 4 let sellTwo = 0, holdTwo = Number.MIN_SAFE_INTEGER; 5 let sellOne = 0, holdOne = Number.MIN_SAFE_INTEGER; 6 7 for (let price of prices) { 8 sellTwo = Math.max(sellTwo, holdTwo + price); 9 holdTwo = Math.max(holdTwo, sellOne - price); 10 sellOne = Math.max(sellOne, holdOne + price); 11 holdOne = Math.max(holdOne, -price); 12 } 13 14 return sellTwo; 15};
C# Solution
1
2csharp
3public class Solution {
4 public int MaxProfit(int[] prices) {
5 int sellTwo = 0, holdTwo = Int32.MinValue;
6 int sellOne = 0, holdOne = Int32.MinValue;
7
8 foreach (int price in prices) {
9 sellTwo = Math.Max(sellTwo, holdTwo + price);
10 holdTwo = Math.Max(holdTwo, sellOne - price);
11 sellOne = Math.Max(sellOne, holdOne + price);
12 holdOne = Math.Max(holdOne, -price);
13 }
14
15 return sellTwo;
16 }
17}
Note: Each solution initializes holdOne
and holdTwo
to the minimum possible integer values. This is because we have not yet bought any stock and hence, we cannot calculate profit at this stage. Similarly, all sell
states are initialized to 0, as we have not made any profit yet.# Time and Space Complexity
Time complexity of this algorithm is O(n), where n is the number of days. This is because we are iterating the price array only once.
Space complexity is O(1) because we are using only a constant amount of space to store our variables (sellTwo, holdTwo, sellOne, holdOne
), irrespective of the input size.
Conclusion
The problem of maximizing profit by buying and selling stocks with at most two transactions is a classic example of dynamic programming. Exploring the different possible states, buying and selling the stocks, allows us to intuitively arrive at the solution. Our algorithm cleverly keeps track of the maximum profit at every state while iterating over the prices, ensuring that it yields the maximum possible profit at the end.
The provided solutions in different programming languages utilize the same approach, demonstrating the versatility of this algorithm. It's important to understand the logic behind these implementations and how dynamic programming enables us to succinctly solve such problems.
So, the next time you encounter a problem that requires maximizing or minimizing a certain parameter, think about how you can use dynamic programming to simplify your calculations.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.