LeetCode 309. Best Time to Buy and Sell Stock with Cooldown
原题链接
简单
作者:
Biang
,
2024-07-15 20:27:03
,
所有人可见
,
阅读 2
直接定义4个状态
class Solution {
const int INF=0x3f3f3f3f;
public:
int maxProfit(vector<int>& p) {
/*
f(i,0) i天未卖出 未持股 f(i-1,0)
f(i,1) i天卖出 未持股 max{g(i-1,0),g(i-1,1)}+p[i]
g(i,0) i天未买入 持股 max{g(i-1,0),g(i-1,1)}
g(i,1) i天买入 持股 f(i-1,0)-p[i]
属性: 最大利润
*/
int n=p.size();
int f[n+1][2],g[n+1][2];
memset(f,0,sizeof f);
memset(g,0,sizeof g);
g[0][0]=-INF;
g[0][1]=-INF;
f[0][0]=-INF;
f[0][0]=0;
for(int i=1; i<=n; i++){
f[i][0]=max(f[i-1][0],f[i-1][1]);
f[i][1]=max(g[i-1][0], g[i-1][1])+p[i-1];
g[i][0]=max(g[i-1][0], g[i-1][1]);
g[i][1]=f[i-1][0]-p[i-1];
}
return max(f[n][0],f[n][1]);
}
};