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;
}
};