题目描述

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

样例

输入：[1,2,3,0,2]
输出：3 
解释：对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

算法1

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

1. 设状态 $f(i)$ 表示第 $i$ 天结束后不持有股票的最大收益；$g(i)$ 表示第 $i$ 天结束后持有股票的最大收益。
2. 初始时，$f(0) = 0, g(0) = -prices[0]$，其余待定。
3. 转移时，$f(i) = \max(f(i - 1), g(i - 1) + prices[i])$，表示第 $i$ 天什么都不做，或者卖掉持有的股票。
4. $g(i) = \max(g(i - 1), f(i - 2) - prices[i])$，表示第 $i$ 天什么都不做，或者买当天的股票，但需要从上两天的结果转移。注意，如果 $i < 2$，则 $f(i - 2)$ 当做 0。
5. 最终答案为 $f(n - 1)$。

时间复杂度

• 状态数为 $O(n)$，每次转移时间为常数，时间复杂度为 $O(n)$。

空间复杂度

• 需要数组存储状态，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0)
            return 0;

        vector<int> f(n); // 当天不持有
        vector<int> g(n); // 当天持有

        f[0] = 0;
        g[0] = -prices[0];
        for (int i = 1; i < n; i++) {
            f[i] = max(f[i - 1], g[i - 1] + prices[i]);
            if (i >= 2)
                g[i] = max(g[i - 1], f[i - 2] - prices[i]);
            else
                g[i] = max(g[i - 1], -prices[i]);
        }
        return f[n - 1];
    }
};

算法2

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

1. 设状态 $f(i)$ 表示第 $i$ 天，当前结束不持有股票且当前没有发生卖出交易的最大收益；$g(i)$ 表示第 $i$ 天结束后不持有股票，且当前刚刚卖出股票的最大收益；$h(i)$ 表示当前持有股票的最大收益。
2. 转移时 $f(i) = \max(f(i - 1), g(i - 1))$，表示构成第 $i$ 天不持有股票且当天无交易有两种方式，一种是前一天也不持有且前一天没有卖出交易，另一种是前一天持有且前一天刚刚卖出股票；二者取最大值。
3. $g(i) = h(i - 1) + prices[i]$，表示构成第 $i$ 天不持有股票且当天有交易仅有一种方式，即当天卖出前一天持有的股票。
4. $h(i) = \max(h(i - 1), f(i - 1) - prices[i])$，表示构成第 $i$ 天持有股票有两种方式，一种是前一天持有，另一种是前一天不持有且前一天无交易，但这一天刚刚买入。
5. 最终答案为 $\max(f(n - 1), g(n - 1))$，即最后一天不持有股票的两种情况。

时间复杂度

• 状态数为 $O(n)$，每次转移时间为常数，时间复杂度为 $O(n)$。

空间复杂度

• 需要数组存储状态，故空间复杂度为 $O(n)$。
• 注意到状态转移之和前一层有关，故可以优化掉第一维。
• 每次提前取出前一层的值，用其更新为新的值即可。
• 所以空间复杂度可以优化到 $O(1)$。

C++ 代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        const int INF = 1000000000;
        int n = prices.size();
        /*
        if (n == 0)
            return 0;
        vector<int> f(n); // 当天不持有，且当天没有卖出交易
        vector<int> g(n); // 当天不持有，且当天刚卖出
        vector<int> h(n); // 当天持有
        f[0] = 0;
        g[0] = -INF;
        h[0] = -prices[0];
        for (int i = 1; i < n; i++) {
            f[i] = max(f[i - 1], g[i - 1]);
            g[i] = h[i - 1] + prices[i];
            h[i] = max(h[i - 1], f[i - 1] - prices[i]);
        }
        return max(f[n - 1], g[n - 1]);
        */
        int f = 0;
        int g = -INF;
        int h = -INF;
        for (int i = 0; i < n; i++) {
            int new_f = max(f, g);
            int new_g = h + prices[i];
            int new_h = max(h, f - prices[i]);
            f = new_f;
            g = new_g;
            h = new_h;
        }
        return max(f, g);
    }
};