問題
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_D
問題文
が与えられるので、 の最大値を求めてね。
制約
サンプル
I/O 1
6 5 3 1 3 4 3
3
I/O 2
3 4 3 2
-1
考察
でやると間に合わない。
が最小なら が最大になるので、 を更新しながら を計算していけばいい。
コード
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; }