AcWing 1056. 股票买卖 III
原题链接
简单
作者:
我要出去乱说
,
2021-02-03 14:03:38
,
所有人可见
,
阅读 935
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
int p[N], g[N], f[N]; //p股票价格, g前i天, f存后n-i天
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &p[i]);
//求g[i]:在1 ~ i中买卖一次的最大收益
for (int i = 2, minv = p[1]; i <= n; i ++ ) //在第一天买入卖出的收益是0,故从2开始
{
g[i] = max(g[i - 1], p[i] - minv);
minv = min(minv, p[i]);
}
//求f[i]:在i ~ n中买卖一次的最大收益
for (int i = n - 1, maxv = p[n]; i >= 1; i -- )
{
f[i] = max(f[i + 1], maxv - p[i]);
maxv = max(maxv, p[i]);
}
int res = 0;
for (int i = 2; i <= n; i ++ )
res = max(res, g[i] + f[i + 1]); //g[i]表示在前i天完成一次交易最大收益
printf("%d\n", res); //f[i+1]表示从第i+1天到第n天完成一次交易的最大收益
return 0;
}
这个思路也不错
aaa好厉害的思路!!简单清晰
我要给你点个赞