Best Time to Buy and Sell Stock IV

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Thoughts

在基础股票问题上状态增加一个维度, buy[i][j]表示ith持有股票且当前最多交易j次时的最大profit. 注意当k大于n/2时, 意味着每次出现prices[i] > prices[i -1]时, 我们都可以在i - 1处买入, i处卖出获得sub profit, 不错过任何低买高卖。最大收益也就是所有sub的和。

Code

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        const int N = prices.size();
        if (N == 0) return 0;
        if (k >= N / 2) {
            int res = 0;
            for (int i = 1; i < N; ++i) {
                if (prices[i] > prices[i - 1]) res += prices[i] - prices[i - 1];
            }
            return res;
        }
        vector<vector<int>> buy(N, vector<int>(k + 1)), sell(N, vector<int>(k + 1));
        for (int j = 0; j <= k; ++j) buy[0][j] = -prices[0];
        for (int i = 1; i < N; ++i) buy[i][0] = max(-prices[i], buy[i - 1][0]);
        for (int i = 1; i < N; ++i) {
            for (int j = 1; j <= k; ++j) {
                buy[i][j] = max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
                sell[i][j] = max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);
            }
        }
        return sell[N - 1][k];
    }
};

Analysis

时间复杂度O(Nk).