D - Maximum Profit

問題

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_D (新しいタブで開く)

問題文

$R_t$ が与えられるので、 $R_j - R_i (j > i)$ の最大値を求めてね。

制約

• $2 \le n \le 200000$
• $1 \le R_t \le 10^9$

サンプル

I/O 1

6
5
3
1
3
4
3

3

I/O 2

3
4
3
2

-1

考察

$O(n^2)$ でやると間に合わない。
$R_i$ が最小なら $R_t - R_i$ が最大になるので、$R_i$ を更新しながら $R_t - R_i$ を計算していけばいい。

コード

https://onlinejudge.u-aizu.ac.jp/status/users/a01sa01to/submissions/1/ALDS1_1_D/judge/6379628/C++17 (新しいタブで開く)

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  int minim = a[0], ans = -1e9;
  rep(i, n - 1) {
    ans = max(ans, a[i + 1] - minim);
    minim = min(minim, a[i + 1]);
  }
  cout << ans << endl;
  return 0;
}