> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/duo-zhuang-tai-dp/best-time-to-buy-and-sell-stock-iv.md).

# 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).