3092: 最大回撤
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：26
解决：21
题目描述
在金融市场上，经常需要统计一只股票的最大回撤。最大回撤是指投资者在某天买入，在之后的某天卖出，可能造成的最大亏损，它可以反应一只股票在历史上的最坏表现。
给定一个整数序列 �1,�2,�3,⋯,��a1,a2,a3,⋯,an，每个 ��ai 表示同一只股票的在某一天的价格，请计算这只股票的最大回撤。即寻找两个下标满足 1≤�≤�≤�1≤i≤j≤n，且 ��−��ai−aj最大。
给定一个整数序列 �1,�2,�3,⋯,��a1,a2,a3,⋯,an，每个 ��ai 表示同一只股票的在某一天的价格，请计算这只股票的最大回撤。即寻找两个下标满足 1≤�≤�≤�1≤i≤j≤n，且 ��−��ai−aj最大。
输入
第一行：单个整数表示 �n，
第二行：�n 个整数表示 �1,�2,�3,⋯,��a1,a2,a3,⋯,an。
第二行：�n 个整数表示 �1,�2,�3,⋯,��a1,a2,a3,⋯,an。
- 对于 30%30% 的数据，�≤1000n≤1000；
- 对于 60%60% 的数据，�≤10000n≤10000；
- 对于 100%100% 的数据，1≤�≤1000001≤n≤100000，−100000≤��≤100000−100000≤ai≤100000。
输出
单个整数：表示这只股票的最大回撤，如果价格一直上涨，输出 0。
样例输入 复制
5
2 3 7 6 1 样例输出 复制
6提示
样例1：
7-1=6
样例2：
5
1 2 3 4 5
0
没有任何可能造成亏损的机会，所以是0
样例3：
5
1 10 100 10 -100
200
7-1=6
样例2：
5
1 2 3 4 5
0
没有任何可能造成亏损的机会，所以是0
样例3：
5
1 10 100 10 -100
200