AOJ-ALDS1

Maximum Profit

  Aizu - ALDS1_1_D 

You can obtain profits from foreign exchange margin transactions. For example, if you buy 1000 dollar at a rate of 100 yen per dollar, and sell them at a rate of 108 yen per dollar, you can obtain (108 - 100) × 1000 = 8000 yen.

Write a program which reads values of a currency RtRt at a certain time tt (t=0,1,2,...n−1t=0,1,2,...n−1), and reports the maximum value of Rj−RiRj−Ri where j>ij>i .

Input

The first line contains an integer nn. In the following nn lines, RtRt (t=0,1,2,...n−1t=0,1,2,...n−1) are given in order.

Output

Print the maximum value in a line.

Constraints

2≤n≤200,0002≤n≤200,0001≤Rt≤1091≤Rt≤109

Sample Input 1

6 5 3 1 3 4 3

Sample Output 1

3

Sample Input 2

3 4 3 2

Sample Output 2

-1

问题链接：AOJ-ALDS1_1_D Maximum Profit

问题简述：

  给定一组数，计算它们的最大差值。

问题分析：

  本题的关键是设计一个时间复杂度为O(n)的算法。

  如果简单地用暴力法来解就Out了！

  最大差值有可能是负数，需要注意。

程序说明：

  最大值的初值应该其变量类型的最小值，使用头文件limits.h中预先定义的值是一种好的选择。

题记：（略）

参考链接：（略）

AC的C++语言程序如下：

/* AOJ-ALDS1_1_D Maximum Profit */ #include <iostream> #include <limits.h> using namespace std; const int N = 2e5; int r[N]; int main() { int n; cin >> n; for(int i=0; i<n; i++) cin >> r[i]; int maxval = INT_MIN; int minval = r[0]; for(int i=1; i<n; i++) { maxval = max(maxval, r[i] - minval); minval = min(minval, r[i]); } cout << maxval << endl; return 0; }