Uva 11078 - Open Credit System

題目

Problem

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

想法

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

推薦文章