设最大的利益为maxv，最小值为minv

1.求最大利益的简单算法

 

 for j从1到n-1                                                for(j=1;j<=n-1;j++)
     for i从0到j-1                                                for(i=0;i<=j-1;i++)
          maxv =（maxv与R[j]-R[i]中较大的一个）                     　　maxv=max(maxv,R[i]-minv);

 

　　 这个算法中，我们将所有满足 i < j 的 i 与 j 的组合全部列了出来，并从中搜索Rj-Ri的最大值maxv。
　　这里一定要注意，maxv必须选择一个合适的初始值。由于 Rt ≤ 109，再考虑到最大利益为负的情况，所以maxv的初始值要低于10-9。
或者可以直接将R1-R0作为初始值。
　　这个算法虽然可以正确输出，但其时间复杂度高达O(n2)，考虑到输入上限( n ≤ 20 000)的问题，会发现当输入较大时，该程序无法在限制之间内完成处理。
一次我们需要研究一种更高效的办法。 

2.求最大利益的改良算法

 minv = R[0]                                                minv = R[0];
 for j从1从n-1                                               for(j=1;j<n;j++)
     maxv =（maxv与R[j]-minv之间较大的一个）                   　　maxv = max(maxv,R[j]-minv);
     minv =（minv与R[j]之间较小的一个）                            minv = min(minv,R[j])；

　　原先的简单算法是关于n的二重循环，时间复杂度为O(n2)。经过我们改良之后，算法中仅包含一个循环，时间复杂度降至O(n)。

另外，改良后的算法不需要将输入的数据保留在数组中，因此同时改善了内存使用量。

例题

输入 第一行输入整数n。接下来n行依次给整数Rt（t = 0，1，2，······，n-1）赋值。
输出 在单独的一行中输出最大值。
限制 2 ≤ n ≤ 200 000
1 ≤ Rt ≤ 109
 

输入示例1

6
5
3
1
3
4
3
输出示例1 
3
 
输入示例2 
3
4
3
2

 输出示例2

-1

 

 C++代码

 #include <bits/stdc++.h>
 using namespace std;
 static const int MAX = 200000;
 int main()
 {
     int R[MAX],n;
     cin>>n;
     for(int i=0;i<n;i++)
         cin>>R[i];
     int maxv= -2000000000;
     int minv= R[0];
     for(int i=1;i<n;i++)
     {
         maxv=max(maxv,R[i]-minv);
         minv=min(minv,R[i]);
     }
     cout<<maxv<<endl;
     return 0;
 }