AcWing 1054. 股票买卖
原题链接
简单
作者:
y总的小迷弟
,
2023-08-05 22:50:48
,
所有人可见
,
阅读 74
//st表瞎搞
#include<bits/stdc++.h>
using namespace std;
int n, ans = 0;
int a[100010];
int f[100010][18];
void init()
{
for(int j = 0;j < 18;j++)
{
for(int i = 1;i + (1 << j) - 1 <= n;i++)
{
if(j == 0)
f[i][j] = a[i];
else
f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
}
}
int query(int l, int r)
{
int len = r - l + 1;
int k = log(len) / log(2);
return max(f[l][k], f[r - (1 << k) + 1][k]);
}
int main()
{
cin >> n;
for(int i = 1;i <= n;i++)
cin >> a[i];
init();
for(int i = 1;i <= n;i++)
{
int t = query(i, n);
ans = max(ans, t - a[i]);
}
cout << ans << endl;
return 0;
}