P5146题解
persimmon2008 · · 题解
题目大意
给一个数组
注意：这个差值仅当
思路
Sub 1： O(n^2)
枚举
显然会超时！
Sub 2: O(n)
通过简单的思考，我们可以容易想到下面这个想法：
用一个数记录当前阶段的最小值，再不断用当前数字更新差值的最大值
坑点
- "
A_i 在 int 范围内"
真的是这样吗，如果我们自觉的开了 int
我们会进一步理解"十年OI一场空，不开 long long 见祖宗"的含义
- 你真的开 long long 了吗
定义变量时，记录最小数的变量是肯定要初始化为 inf 的
而开了 long long 的 inf 便不止 0x7fffffff 了。
Code
#include<iostream>
#include<cstdio>
#define int long long
#define inf 0x7ffffffffffffff
#define Min(a,b) a<b?a:b
#define Max(a,b) a>b?a:b
using namespace std;
inline int read() {
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s*w;
}
inline void write(int x) {
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
signed main() {
int n=read(),minn=inf,maxn=0;
while(n--){
int x=read();
maxn=Max(maxn,x-minn);
minn=Min(minn,x);
}
write(maxn);
return 0;
}