和不同的是,这边不再限制k,但除了有货和无货外还多了一个冷冻期的状态。
用0表示有货,1表示无货,2表示冷冻期。
f[i, 0], f[i, 1], f[i, 2]分别表示经过i天,且第i天处于有货、无货、冷冻期状态。
一开始手中是无货的,所以入口在无货状态。
因为手中有货必然是花钱买的,不卖出只会比卖出亏,所以出口只有无货和冷冻期。
换成初始化就是f[0][0] = 0
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size(), ans = 0;
vector<vector<int>> f(n + 1, vector<int>(3, -0x3f3f3f3f));
f[0][0] = 0;
for (int i = 1; i <= n; i ++) {
int p = prices[i - 1];
f[i][0] = max(f[i - 1][2], f[i - 1][0]);
f[i][1] = max(f[i - 1][0] - p, f[i - 1][1]);
f[i][2] = f[i - 1][1] + p;
ans = max(ans, max(f[i][0], f[i][2]));
}
return ans;
}
};
滚动数组优化
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size(), ans = 0;
int f[3], g[3];
g[0] = 0;
g[1] = g[2] = -0x3f3f3f3f;
for (int i = 1; i <= n; i ++) {
int p = prices[i - 1];
f[0] = max(g[2], g[0]);
f[1] = max(g[0] - p, g[1]);
f[2] = g[1] + p;
ans = max(ans, max(f[0], f[2]));
memcpy(g, f, sizeof(f));
}
return ans;
}
};
因篇幅问题不能全部显示,请点此查看更多更全内容
怀疑对方AI换脸可以让对方摁鼻子 真人摁下去鼻子会变形
女子野生动物园下车狼悄悄靠近 后车司机按喇叭提醒
睡前玩8分钟手机身体兴奋1小时 还可能让你“变丑”
惊蛰为啥吃梨?倒春寒来不来就看惊蛰
男子高速犯困开智能驾驶出事故 60万刚买的奔驰严重损毁