Interview Classic 150 Questions P188 Best Time to Buy and Sell Stock IV

---

Timeline

timeline

2025-12-17

init

dynamic programming

---

Problem:

P188 Best Time to Buy and Sell Stock IV

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/?envType=study-plan-v2&envId=top-interview-150

Similar to the following problem:

P123 Best Time to Buy and Sell Stock III

https://even629.com/posts/123/

#include <vector>
#include <algorithm>
using std::vector;

class Solution {
    public:
        int maxProfit(int k, vector<int> &prices)
        {
                int i, j, n = prices.size();
                int nr_state = 2 * k + 1;
                if (n == 1) {
                        return 0;
                }
                // dp[i][j] represents the maximum profit on the i-th day in the j-th state
                vector<vector<int> > dp(n, vector<int>(nr_state, 0));
                dp[0][0] = 0;
                dp[0][1] = -prices[0];
                for (j = 2; j < nr_state; j++) {
                        dp[i][j] = -1e9;
                }

                for (i = 1; i < n; i++) {
                        dp[i][0] = dp[i - 1][0];
                        for (j = 1; j < nr_state; j += 2) {
                                dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                        }
                        for (j = 2; j < nr_state; j += 2) {
                                dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
                        }
                }
                return *std::max_element(dp[n - 1].begin(), dp[n - 1].end());
        }
};