YunheWang0813
3/29/2020 - 6:31 AM

0123. Best Time to Buy and Sell Stock III

class Solution {
public:
    int maxProfit(vector<int>& P) {
        if (P.size() == 0) return 0;
        int n = P.size();
        vector<vector<int>> f(n + 1, vector<int>(6));
        for (int i = 1; i <= 5; i++) {
            f[0][i] = INT_MIN;
        }
        f[0][1] = 0;
        for (int i = 1; i <= n; i++) {
            // Step 1, 3, 5 (no stock)
            // 没有股票,说明: 1. 昨天也没有 2. 卖掉了昨天的(可获利)
            // TF: f[i][j] = max{f[i-1][j], f[i-1][j-1] + Pi-1 - Pi-2}
            for (int j = 1; j <= 5; j += 2) {
                f[i][j] = f[i - 1][j];
                if (i > 1 && j > 1 && f[i - 1][j - 1] != INT_MIN) {
                    f[i][j] = max(f[i][j], f[i - 1][j - 1] + P[i - 1] - P[i - 2]);
                }
            }
            // Step 2, 4 (have stock)
            // 有股票,说明: 1. 昨天也有(可获利) 2. 昨天没有,今天买了
            // TF: f[i][j] = max{f[i-1][j-1], f[i-1][j] + Pi-1 - Pi-2}
            for (int j = 2; j <= 5; j += 2) {
                f[i][j] = f[i - 1][j - 1];
                if (i > 1 && f[i - 1][j] != INT_MIN) {
                    f[i][j] = max(f[i - 1][j] + P[i - 1] - P[i - 2], f[i][j]);
                }
            }
        }
        int res = 0;
        for (int i = 1; i <= 5; i += 2) {
            res = max(res, f[n][i]);
        }
        return res;
    }
};