其实这个和 Python 没太大关系, 发到解题板之类的可能更好
不过简单的做法大概是这样
※ 引述《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 当最小值 然后往右找最大
: 最后在看哪个最小
要扫一次 list 基本是无法避免
所以重点就是决定每个 index 的最小值后不要再回头找最大值
而是要记住之前找过的最大值重复利用
这样就可以 O(n)
: 但是有没有更好或是更快的方法？
: 感谢
其实你的最小值从后面扫回来会比较好想：
有 [38, 45, 22, 1, 19, 15, 23, 60, 46, 15]
要找到 max 在 min 的“左边”（前面）
这样你就会发现其实你一直在扫重复的东西
重点是, 当你往前找下一个最小值时
下一个最小值可以用的可能最大值一定是 max(前一个最大值, 前一个最小值)
例如上面第三项是 22, 可以用来比的是 38, 45, 所以最大值是 45
第四项是 1, 可以来比的就是上面那两个与第三项, 所以最大值是 max(45, 22) = 45
所以你只要记住循环上一轮找到的最大最小值, 就可以不用一直往前重扫
(故意不放程式, 自己想吧)
====
But, 人生就是这个 but
上面那个方法基本上要用 Python 的 for 实作
如果你的 list 不长, 说不定这样还比较快...
max(
max(b - a for b in numbers[i:] or [float('-inf')])
for i, a in enumerate(numbers)
)
这基本上就是你一开始的 O(n^2) 暴力法
但因为 max 用的是 C 的 for 循环, 直接就打趴 Python 好几条街了...