问题 A: 最大回撤

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:26 解决:21

题目描述

在金融市场上,经常需要统计一只股票的最大回撤。最大回撤是指投资者在某天买入,在之后的某天卖出,可能造成的最大亏损,它可以反应一只股票在历史上的最坏表现。


给定一个整数序列 �1,�2,�3,⋯,��a1,a2,a3,,an,每个 ��ai 表示同一只股票的在某一天的价格,请计算这只股票的最大回撤。即寻找两个下标满足 1≤�≤�≤�1ijn,且 ��−��aiaj最大。


输入

第一行:单个整数表示 n
第二行:n 个整数表示 �1,�2,�3,⋯,��a1,a2,a3,,an


  • 对于 30%30% 的数据,�≤1000n1000
  • 对于 60%60% 的数据,�≤10000n10000
  • 对于 100%100% 的数据,1≤�≤1000001n100000−100000≤��≤100000100000ai100000


输出

单个整数:表示这只股票的最大回撤,如果价格一直上涨,输出 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