ALDS1_1_D:

この問題では、$maxv$ を最大利益とすると、次のアルゴリズムで条件を満たす正しい出力を得ることができます。

for j が 1 から n-1 まで
  for i が 0 から j-1 まで
    maxv = (maxv と R[j]-R[i] のうち大きい方)

このアルゴリズムは、$i < j$ となるような $i$ と $j$ の全ての組に対する $R_j − R_i$ を調べて最大値 $maxv$ を求めています。

ここでひとつ気を付けなければならないことは、$maxv$ の初期値を適切に設定することです。$R_t \leq 10^9$ なので、最大の利益が負になることを考慮して、$maxv$ の初期値は $10^9 \times(−1)$ 以下にする必要があります。あるいは、$R_1 − R_0$ を初期値としてもよいでしょう。

このアルゴリズムでは確かに正しい出力が得られますが、その計算量は $O(n^2)$ であり、入力の上限 ($n \leq 200,000)$ を考慮すると、大きな入力に対しては制限時間内に処理を終えることはできません。そこで、より高速なアルゴリズムを検討しましょう。

知りたい値は $j$ よりも前方の最小値なのですが、それを上のような素朴なアルゴリズムで求めると $O(n)$ かかり、これを各 $j$ について毎回行うと $O(n^2)$ の計算量になってしまいます。しかしこれは、$j$ を増やす過程で、それ以前の $R_j$ の最小値（これを $minv$ とします）を保持しておくことで、時刻 $j$ における最大利益を $O(1)$ で求めることができます。ここで、$O(1)$ は入力の大きさに影響しない一定の計算量を表します。

最大利益の更新判定を $n$ 回行えばよいので、次のようなアルゴリズムになります。

minv = R[0]
for j が 1 から n-1 まで
  maxv = (maxv と R[j]-minv のうち大きい方)
  minv = (minv と R[j] のうち小さい方)

$n$ に関する２重ループで実装された $O(n^2)$ の素朴なアルゴリズムを、ひとつのループで完結した $O(n)$ のアルゴリズムに改良することができました。また、改良したアルゴリズムでは、入力を配列に保持する必要もなくなり、メモリ使用量も改善することができます。

Reference

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (マイナビ) AIZU ONLINE JUDGE のコース問題を題材にした解説書です。初級者が体系的にアルゴリズムとデータ構造の基礎を学ぶことができる入門書となっています。