1. 买卖股票的最佳时机

买卖股票的最佳时机
正向思维：我今天买了，遍历之后的每天找到最大值卖出即可。
逆向思维：我在第i天卖掉，要想获得最大利润，需要在之前的最低点买入。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        int prvMin = INT_MAX;
        for (int i = 0; i < prices.size(); i++) {
            profit = max(profit, prices[i] - prvMin);
            prvMin = min(prvMin, prices[i]);
        }
        return profit;
    }
};

2. 买卖股票的最佳时机 II

买卖股票的最佳时机 II

class Solution {
public:
    int maxProfit(vector<int>& p) {
        int ret = 0, n = p.size();
        for (int i = 0; i < n; i++) {
            int j = i;
            while (j + 1 < n && p[j + 1] > p[j])
                j++;
            ret += p[j] - p[i];
            i = j;
        }
        return ret;
    }
};
// class Solution {
// public:
//     int maxProfit(vector<int>& prices) {
//         int ret = 0;
//         for (int i = 1; i < prices.size(); i++) {
//             if (prices[i] > prices[i - 1])
//                 ret += prices[i] - prices[i - 1];
//         }
//         return ret;
//     }
// };

3. 买卖股票的最佳时机 III

买卖股票的最佳时机 III

class Solution {
public:
    // f[i][j]表⽰：第i天结束后，完成了j次交易，处于「买⼊」状态，此时的最⼤利润；
    // g[i][j]表⽰：第i天结束后，完成了j次交易，处于「卖出」状态，此时的最⼤利润
    const int INF = 0x3f3f3f3f;
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(3, -INF));
        auto g = f;
        f[0][0] = -prices[0], g[0][0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = j >= 1 ? max(g[i - 1][j], f[i - 1][j - 1] + prices[i])
                                 : g[i - 1][j];
            }
        }
        // 找到最后⼀⾏的最⼤值
        int ret = 0;
        for (int j = 0; j < 3; j++)
            ret = max(ret, g[n - 1][j]);
        return ret;
    }
};

4. 买卖股票的最佳时机 IV

买卖股票的最佳时机 IV

class Solution {
    // f[i][j]表⽰：第i天结束后，完成了j笔交易，此时处于「有股票」状态的最⼤收益；
    // g[i][j]表⽰：第i天结束后，完成了j笔交易，此时处于「⽆股票」状态的最⼤收益。
public:
    int maxProfit(int k, vector<int>& prices) {
        const int INF = 0x3f3f3f3f;

        // 处理⼀个细节问题
        int n = prices.size();
        k = min(k, n / 2);
        vector<vector<int>> f(n, vector<int>(k + 1, -INF));
        auto g = f;
        f[0][0] = -prices[0], g[0][0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = j >= 1 ? max(g[i - 1][j], f[i - 1][j - 1] + prices[i])
                                 : g[i - 1][j];
            }
        }
        int ret = 0;
        for (int j = 0; j <= k; j++)
            ret = max(ret, g[n - 1][j]);
        return ret;
    }
};

5. 买卖股票的最佳时机含冷冻期

买卖股票的最佳时机含冷冻期

class Solution {
// dp[i][0] 表⽰：第i 天结束后，处于「买⼊」状态，此时的最⼤利润；
// dp[i][1] 表⽰：第i 天结束后，处于「可交易」状态，此时的最⼤利润；
// dp[i][2] 表⽰：第i 结束后，处于「冷冻期」状态，此时的最⼤利润
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(3));
        dp[0][0] = -prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + prices[i];
        }
        return max(dp[n - 1][1], dp[n - 1][2]);
    }
};

6. 买卖股票的最佳时机含手续费

买卖股票的最佳时机含手续费

class Solution {
// f[i] 表⽰：第i天结束后，处于「买⼊」状态，此时的最⼤利润；
// g[i] 表⽰：第i天结束后，处于「卖出」状态，此时的最⼤利润。
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<int> f(n);
        auto g = f;
        f[0] = -prices[0];
        for (int i = 1; i < n; i++) {
            f[i] = max(f[i - 1], g[i - 1] - prices[i]);
            g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee);
        }
        return g[n - 1];
    }
};