alan23273850 的刷題筆記
c435: MAX ! MAX ! MAX !
出處：https://zerojudge.tw/ShowProblem?problemid=c435
提交：https://zerojudge.tw/Submissions?problemid=c435&account=allllllan123456
問題：給定 $n\in[2,100000]$ 個介於 $[1,100000]$ 的正整數 a[1:n]，試求最大的 a$[i]$ - a$[j]$，如果 1 $\le$ $i$ $\lt$ $j$ $\le$ n。
解法：這題的 DP 設計和 d784、a540 極為類似，也是不用陣列就能實作，只要掌握住 $\underset{1\ \le\ i\ \lt\ j}{\max}\{\ a[i]-a[j]\ \} = \Big(\underset{1\ \le\ i\ \lt\ j}{\max}\ a[i]\ \Big) - a[j]$ 的技巧，那麼從左往右掃的過程中每次就可以固定好當下的 $j$ 以算出答案。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int n;
6 while (cin >> n) { n--;
7 int ans=INT_MIN, maX; cin >> maX;
8 while (n--) {
9 int a; cin >> a;
10 ans = max(ans, maX - a);
11 maX = max(maX, a);
12 }
13 cout << ans << '\n';
14 }
15 return 0;
16}