算法提高之股票买卖 V
-
核心思想:状态机
- 一共有三种情况 : 空仓,持仓,冻结期
- f[i,j]表示第i天的状态j
- 状态计算: 如下
-
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 100010; int f[N][3]; int w[N]; int n; int main() { cin>>n; for(int i=0;i<n;i++) cin>>w[i]; f[0][0] = 0; f[0][1] = -w[0]; for(int i=1;i<n;i++) { //当前空仓 = 前一次空仓/前一次冻结期 f[i][0] = max(f[i-1][0] , f[i-1][2]); //当前持仓 = 前一次持仓/前一次空仓买入 f[i][1] = max(f[i-1][1] , f[i-1][0] - w[i]); //当前冻结期 = 前一次持仓卖出 f[i][2] = f[i-1][1] + w[i]; } cout<<max(f[n-1][0],f[n-1][2])<<endl; return 0; }