一种常用的方法是将「买入」和「卖出」分开进行考虑：「买入」为负收益，而「卖出」为正收益。在初入股市时，你只有「买入」的权利，只能获得负收益。而当你「买入」之后，你就有了「卖出」的权利，可以获得正收益。显然，我们需要尽可能地降低负收益而提高正收益，因此我们的目标总是将收益值最大化。因此，我们可以使用动态规划的方法，维护在股市中每一天结束后可以获得的「累计最大收益」，并以此进行状态转移，得到最终的答案。

官方解答

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (!n) return 0;
        vector<vector<int>> f(n, vector<int>(3, INT_MIN));
        f[0][0] = 0, f[0][1] = -prices[0];
        for (int i = 1; i < n; i ++) {
            f[i][0] = max(f[i - 1][0], f[i - 1][2]);
            f[i][1] = max(f[i - 1][0] - prices[i], f[i - 1][1]);
            f[i][2] = f[i - 1][1] + prices[i];
        }
        return max(f[n - 1][0], max(f[n - 1][1], f[n - 1][2]));
    }
};

dp 含义 第 i 天结束之后的「累计最大收益」

还是很好理解的

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        // f[i][?] 的含义是 第 i 天结束后的累计收益(支出为负收益)
        vector<vector<int>> f(n, vector<int>(3));
        // f[0][0] = 0; // 进入冷静期
        // f[0][1] = 0; // 未持有股票，不进入冷静期
        f[0][2] = -prices[0]; // 持有股票
        for (int i = 1; i < n; i ++) {
            // 今天结束进入冷静期了，说明今天出售了股票
            f[i][0] = f[i - 1][2] + prices[i];
            // 可能是延续了之前未持有的状态，也可能是冷静期结束，
            f[i][1] = max(f[i - 1][0], f[i - 1][1]);
            // 可能是延续了之前持有的状态，或者今天购买了股票
            f[i][2] = max(f[i - 1][2], f[i - 1][1] - prices[i]);
        }
        return max(f[n - 1][0], f[n - 1][1]);
    }
};