這題與「最大子數列和問題」相似，可以使用類似的策略解題

如果你不知道什麼是最大數序列和問題，可以參考 zerojudge 上的這題： d784

同時，我個人也建議你先去解那題，再回來寫這題。

一般的暴力解很簡單，雙層 for 迴圈窮舉所有數字相減的結果，取最大值就是答案，時間複雜度是 O(n^2)

輕鬆，簡單，但會吃 TLE

因為測資中的學生人數最大有可能有 100000 個這麼多，且包含多組測資，如果每組都這麼長，那就會算到天荒地老，所以我們需要一個更快的算法。

卡丹算法 (Kadane's Algorithm) 就是一個很簡單的做法，時間複雜度為 O(n)

這是一個用來計算最大子數列和問題的算法，稍微修改一下就能用在這題

最大子數列和問題

簡述什麼是「最大子數列和問題」

有一個一維數列，所有元素均為整數，找出該數列連續元素的和的最大值。

例如 [-2,1,-3,4,-1,2,1,-5,4] 的最大子數列為 [4,-1,2,1]，最大子數列和為 6

卡丹算法解最大子數列和問題

(這裡不討論為什麼能這樣做，因為 d784 那題已經有很多資源可以參考了)

使用卡丹算法解最大子數列問題時，我們會需要維護兩個變量

• 最大子數列和 result
• 暫時的最大和 temp

這兩個變量的值都預設為 0

然後 for 循環陣列，每讀一個數字 num 就做下面的事情：

• 將 num 與 temp 相加
• 比較 num + temp 和 num 的大小，取比較大的值取代 temp
• 比較 temp 和 result 的大小，取比較大的值取代 result

遍歷完後輸出 result 即為正解

時間複雜度 O(n)

修改卡丹算法，解區間最大差問題

我們可以利用類似的思路去解這題，稍加修改即可

在這題中，我們需要維護兩個變量：

• result 代表最終結果，整個數列的最大差
• curr_max 代表當前最大值

result 預設為負無限，python 可以這樣寫 result = float('-inf')

curr_max 預設為數列中第一個數字的值

然後 for 循環該數列，從第 1 個位置開始讀 (不是第 0 個)，每讀一個數字 num 就做下面的事情：

• 比較 result 和 curr_max - num 的大小，若 curr_max - num 比較大，則讓 curr_max - num 取代 result
• 比較 curr_max 和 num 的大小，若 num 比較大，就讓 num 取代 curr_max

最後輸出 result 即為正解

時間複雜度 O(n)

--

參考答案: gist 連結

LeetCode 上類似的題目: 121. Best Time to Buy and Sell Stock

最後提醒 python 使用者，如果想去 UVa 玩這題，注意 ZeroJudge 和 UVa 的測資格式是不同的