※ 引述《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 的索引值