P5146 最大差值
题目描述
HKE最近热衷于研究序列，有一次他发现了一个有趣的问题：
对于一个序列(A_1,A_2cdots A_n)，找出两个数(i,j)，(1leq i<jleq n)，使得(A_j-A_i)最大。
现在给出这个序列，请找出(A_j-A_i)的最大值。
输入格式
第一行为一个正整数(n)。
接下来(n)行整数，第(k+1)行的整数为(A_k)。
输出格式
一行为((A_j-A_i))的最大值
输入输出样例
输入 #1
10
1 3 4 6 7 9 10 1 2 9
输出 #1
9
说明/提示
对于30%的数据，(nleq1000)
对于70%的数据，(nleq100000)
对于100%的数据，(2leq nleq1000000)，(A_i)的值在int范围内
【思路】
贪心
【题目大意】
求这一串数字里面任意两个数差最大是多少
【题目分析】
因为是任意两个数
没有区间长度的限制
所以用不到单调队列
当前的数一定是在减去前面最小的那个数的情况最优
（包括自己）
这样只需要用一个变量
来记录到目前为止最小的数就好了
每一次的差都比较一下
最后输出差最大的值
【完整代码】
#include<iostream>
#include<cstdio>
using namespace std;
const int Max = 1000006;
int a[Max];
int main()
{
int n;
cin >> n;
for(register int i = 1;i <= n;++ i)
cin >> a[i];
int M = a[1];
int ans = 0;
for(register int i = 1;i <= n;++ i)
{
M = min(M,a[i]);
ans = max(ans,a[i] - M);
}
cout << ans << endl;
return 0;
}