AcWing 1056. 股票买卖 III-前后缀分解代码
原题链接
简单
作者:
AndSonder
,
2022-02-22 17:19:01
,
所有人可见
,
阅读 212
代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10, INT_MIN = -0x3f3f3f3f,INT_MAX = 0x3f3f3f3f;
int num[N];
int f[N];
int main()
{
int n;
cin >> n;
for(int i = 1;i <= n;i++) cin >> num[i];
for(int i = 1,minp = INT_MAX;i <= n;i++)
{
f[i] = max(f[i-1], num[i] - minp);
minp = min(minp,num[i]);
}
int res = 0;
for(int i = n,maxp = INT_MIN;i >= 1;i--)
{
res = max(res, f[i-1] + maxp - num[i]);
maxp = max(maxp, num[i]);
}
cout << res;
return 0;
}