相邻两天,若后一天的价格大就卖出,分析到这里,就可以从第2天枚举,只要比前一天大就买入,卖出,记录差值。
#include <iostream>
using namespace std;
const int N = 1e5+10;
int w[N], n;
int main()
{
cin >> n;
for (int i = 0; i < n; i++) cin >> w[i];
int res = 0;
for (int i = 1; i < n; i++)
{
int t = w[i] - w[i-1];
if (t > 0) res += t;
}
cout << res;
return 0;
}
dp 状态机
#include <iostream>
using namespace std;
const int N = 1e5+10, INF = -0x3f3f3f3f;
int f[N][2], n; //f[i, j]:第i 天股票,状态为j, 1:持有,0:不持有,属性:求总价值最大
int w[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];
f[0][1] = INF; //第0天持有的状态不合法
for (int i = 1; i <= n; i++)
{
f[i][0] = max(f[i-1][1] + w[i], f[i-1][0]);
f[i][1] = max(f[i-1][0] - w[i], f[i-1][1]);
}
cout << f[n][0]; //第n天股票全部卖出
return 0;
}