【題目敘述】
https://vjudge.net/problem/UVA-11078 (考生答對率: 12.77%)
i959: 11078 – Open Credit System
【解題想法】依題意 2 <= n <= 100,000，須避免重複的計算，否則會TLE。使用兩個set（st1 和 st2），st1 紀錄已經出現過的學生成績，*st1.rbegin() 的值即為目前為止最高分數。當有新同學加入時（分數 x），只要計算 (*st1.rbegin()) – x 的值，即為新同學與所有老同學的分數差距最大值。再把這個分數差距值紀錄於 st2，最後 *st2.rbegin() 即為答案。
#include <iostream>
#include <set>
using namespace std;
int T, n, x;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> T;
while (T--) {
cin >> n;
set <int> st1, st2;
cin >> x;
st1.insert(x); //senior
for (int i = 1; i < n; i++) {
cin >> x;
st2.insert((*st1.rbegin()) - x); //max(senior - junior)
st1.insert(x);
}
cout << *st2.rbegin() << "\n";
}
return 0;
}