Uva 11078 - Open Credit System

題目

Problem#

(簡化)
有一組數列($a_i$)，對所有$i<j$，求最大的$a_i - a_j$

想法#

$\mathcal{O}(n^2)$暴力會TLE，但觀察可以發現，對於每個$a_j$，如果$a_i - a_j$要最大，那$a_i$一定越大越好，所以可以直接維護一個最大值($M$)，代表從$1 \sim i$的最大。
只要掃一遍，就得到答案。($\mathcal{O}(n)$)

AC Code#

https://github.com/roy4801/solved_problems/blob/master/uva/11078.cpp

其他解法#

單調隊列
https://csy54.github.io/2019/02/UVa-11078/

https://gist.github.com/roy4801/b417a1a65d2e43f3534f580a3bacd78d