Description Link to heading

188. Best Time to Buy and Sell Stock IV (Hard)

You are given an integer array prices where prices[i] is the price of a given stock on the iᵗʰ day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times.

Note: 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.

Constraints:

  • 1 <= k <= 100
  • 1 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000

Solution Link to heading

Firstly, we may categorize the status of stocks into two states: the acquired and unheld states. Given that a maximum of $k$ transactions can be executed, we thereby have a total of $2k$ potential states.

Hence, it is plausible to instantiate an array as follows: vector<vector<int>> dp(n, vector<int>(2 * k + 1)). Employing dynamic programming, this conundrum is resolvable. The rationale behind selecting an array length of $2k + 1$ is to accommodate negative indices when transitioning from known states.

123. Best Time to Buy and Sell Stock III and 309. Best Time to Buy and Sell Stock with Cooldown both lend themselves to analogous problem-solving approaches.

Code Link to heading 

class Solution {
  public:
    int maxProfit(int k, vector<int> &prices) {
        vector<vector<int>> dp(prices.size() + 1, vector<int>(2 * k + 1, 0));
        for (int j = 1; j <= 2 * k; j++) {
            if (j % 2 == 1)
                dp[0][j] = -prices[0];
        }

        for (int i = 1; i <= prices.size(); i++) {
            for (int j = 1; j <= 2 * k; j++) {
                if (j % 2 == 1)
                    dp[i][j] = max(dp[i - 1][j - 1] - prices[i - 1], dp[i - 1][j]);
                else
                    dp[i][j] = max(dp[i - 1][j - 1] + prices[i - 1], dp[i - 1][j]);
            }
        }
        return dp[prices.size()][2 * k];
    }
};