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.