※ 引述《joe1234wu ()》之銘言：
: 想請教大家....
: 最近遇到一個問題
: 情境會變成
: 有個數列
: ex: [15, 46, 60, 23, 15, 19, 1, 22, 45, 38]
: 我要如何找到 Max and min 使得 Max-min 最大
: 但是 Max 必須在min 的右邊
: 以上面的例子為例
: 就是 Max = 60 min = 15( 因為 60-15 = 45會是最大)
: 我有想過 O(n^2)的方式 就是每次index 當最小值 然後往右找最大
: 最後在看哪個最小
: 但是有沒有更好或是更快的方法？
: 感謝
提供一個 O(n) 解法
想法：
Greedy 的概念，在走訪數列 data 的過程中
假設目前找到的最佳解為 (min, max)，目前走到第 i 個元素
1. 若 data[i] > max
則可以直接更新最佳解為 (min, data[i])
2. 若 data[i] < min
此情形能推測，若之後又出現一個更大的值 x
x - data[i] > x - min 必定會成立
換句話說，用 data[i] 當 min 去往後找 一定比 用目前的 min 往後找 還更好
因此將目前的 (min, max) 列為解答候選人之一
然後改用 (data[i], data[i]) 繼續往後找 (相當於不管前面了直接從這裡開始)
3. 其他情況: 不會影響最佳解
走訪完後，檢查所有解答候選人，最佳的即為答案
實作時只要維護一個指標指向 目前最佳解的 min
然後走訪 data 時，假設當前走到的元素是 max 去更新解答
若當前元素 < 目前最佳解的 min 則更新指向 min 的指標指向當前元素
即可
這樣講實在很抽象，直接看 code
data = [15, 46, 60, 23, 15, 19, 1, 22, 45, 38]
p = 0 # 目前最佳解的 min 的索引值
ans = (0, 0) # (min, max)
for i in range(len(data)):
if data[i] < data[p]:
p = i # 更新最佳解的 min 的索引值
elif data[i] - data[p] > data[ans[1]] - data[ans[0]]:
ans = (p, i) # 更新解答
print('min = data[%s] = %s' % (ans[0], data[ans[0]]))
print('max = data[%s] = %s' % (ans[1], data[ans[1]]))
'''output
min = data[0] = 15
max = data[2] = 60
'''
code 解說 & 拿範例來跑一次
初始化
p = 0 # 目前最佳解的最小值的索引值 (data[p] = 上面提到的 min)
ans = (0, 0) # 記錄解答 min, max 的索引值