Leetcode 123 - Best Time to Buy and Sell Stock III

Link to problem

Description

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Solution

This post is to admire a great explanation on Leetcode. I recommend you skip what I wrote below and take a look at the author’s explanation.

It is quite obvious that this problem could be solved with Dynamic Programming. But figuring out the solution is still hard.

The basic idea of this solution is to think about how many condition need to take into consideration when deciding to buy / sell / hold the stock.

1. Stock price on ith day.
2. Number of stock transactions done already.
3. Currently holding / not holding a stock.

Since there are three conditions to think about, the DP table should be three dimension. Or you could create 2 DP tables representing the current profit when holding 0 / 1 stock.

Let dpNoStock[i][j] and dpHoldStock[i][j] be the maximum profit of ith day and have done j transactions when not holding / holding a stock. Each day we should maximize our profit by deciding if we should hold / buy / sell a stock.

dpNoStock should be initialized with 0 while dpHoldStock could be initialized with INT_MIN as to make dpNoStock decide to buy stock (see the recurrence relation below).

The recurrence relation of the DP table should be:

• dpNoStock[i][j] = max(dpNoStock[i-1][j], dpHoldStock[i-1][j] + prices[i])
• dpHoldStock[i][j] = max(dpHoldStock[i-1][j], dpNoStock[i-1][j-1] - prices[i])

As you may see from the recurrence relation, the DP table could also be further optimized only a set of values are used in each iteration, making space complexity $O(1)$. However, the original version is more general that it could solve problems with k transaction limits.

Finally, the result should be the last element of dpNoStock (of course we shouldn’t be holding any stock at the end).

Implementation

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int dpSize = prices.size() + 1;
        vector<vector<int>> dpNoStock (
            dpSize, vector<int>(2)
        );
        vector<vector<int>> dpHoldStock (
            dpSize, vector<int>(2, INT_MIN)
        );
        // ith day, j transactions done, hold/no stock at hand

        for (int i = 1; i < dpSize; i++) {
            for (int j = 0; j < 2; j++) {
                int profitNotHolding = (j-1 >= 0)? dpNoStock[i-1][j-1]: 0;
                dpNoStock[i][j] = max(dpNoStock[i-1][j], dpHoldStock[i-1][j] + prices[i-1]);     // hold / sell stock
                dpHoldStock[i][j] = max(dpHoldStock[i-1][j], profitNotHolding - prices[i-1]);    // hold / buy stock
            }
        }

        return dpNoStock.back().back();
    }
};

Optimized

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int noStock1 = 0, noStock2 = 0;                     // 1, 2 denotes the number of transactions done
        int holdStock1 = INT_MIN, holdStock2 = INT_MIN;

        for (auto i: prices) {
            noStock2 = max(noStock2, holdStock2 + i);
            holdStock2 = max(holdStock2, noStock1 - i);
            noStock1 = max(noStock1, holdStock1 + i);
            holdStock1 = max(holdStock1, -i);
        }

        return noStock2;
    }
};

Related Problems

1. 121 - Best Time to Buy and Sell Stock
2. 122 - Best Time to Buy and Sell Stock II
3. 123 - Best Time to Buy and Sell Stock III (you are here)
4. 188 - Best Time to Buy and Sell Stock IV
5. 309 - Best Time to Buy and Sell Stock with Cooldown
6. 714 - Best Time to Buy and Sell Stock with Transaction Fee