题目描述

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意

• 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

样例

输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，
在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2。

输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，
在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4。
随后，在第 5 天 (股票价格 = 0) 的时候买入，
在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3。

算法

(动态规划) $O(nk)$

1. 当 $k \ge n/2$ 时，问题转化为了 Best Time to Buy and Sell Stock II 问题。
2. 否则，仍然可以采用动态规划思路解决问题。
3. 设 $f(i,j)$ 表示第 $i$ 天，交易了 $j$ 次股票，且当天不持有股票的最大收益；$g(i,j)$ 表示第 $i$ 天，交易了 $j$ 次股票，且当天持有股票的最大收益。
4. 初始值 $f(0,0)=0, g(0,0)=-inf$；其余为负无穷。
5. 转移时，$f(i,j) = \max(f(i - 1,j), g(i - 1,j - 1) + prices[i])$，$g(i,j) = \max(g(i - 1,j), f(i - 1,j) - prices[i])$。含义基本和 Best Time to Buy and Sell Stock II 同理。
6. 最终答案为 $\max (f(n,i))$, $0 \le i \le k$。

时间复杂度

• 状态数为 $O(nk)$，转移时间为常数，故总时间复杂度为 $O(nk)$。

空间复杂度

• 需要额外 $O(nk)$ 的空间存储状态。
• 可以通过滚动数组优化到 $O(k)$。

C++ 代码

class Solution {
public:
    const int INF = 1000000000;
    int maxProfitII(vector<int>& prices) {
        int n = prices.size();
        int f = 0, g = -INF;

        for (int i = 0; i < n; i++) {
            int last_f = f, last_g = g;
            f = max(last_f, last_g + prices[i]);
            g = max(last_g, last_f - prices[i]);
        }
        return f;
    }
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (k >= n / 2)
            return maxProfitII(prices);

        vector<vector<int>> f(2, vector<int>(k + 1, -INF));
        vector<vector<int>> g(2, vector<int>(k + 1, -INF));
        f[0][0] = 0;

        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= k; j++) {
                f[i & 1][j] = f[i - 1 & 1][j];
                g[i & 1][j] = max(g[i - 1 & 1][j], f[i - 1 & 1][j] - prices[i - 1]);

                if (j > 0)
                    f[i & 1][j] = max(f[i & 1][j], g[i - 1 & 1][j - 1] + prices[i - 1]);
            }

        int ans = 0;
        for (int i = 0; i <= k; i++)
            ans = max(ans, f[n & 1][i]);

        return ans;
    }
};