[問題] 如何在數列中找到max min且max在min右邊

[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 當最小值 然後往右找最大
最後在看哪個最小

但是有沒有更好或是更快的方法？

感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.228.106.198
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1439825075.A.20F.html
推 ckc1ark: 掃一遍記錄目前看過的最小值 再和目前的值相減找最大?
→ ckc1ark: 你的目標應該是找ai和aj (j>i)然後maximize(aj-ai)吧 和m
→ ckc1ark: ax min有關係嗎
→ joe1234wu: 對 樓上的敘述比較對 但是無法照你第一樓說的方法做
推 ckc1ark: 我指的是每看一個值就當aj, ai當然不意外是已經看過的(a1
→ ckc1ark: ~j-1)最小值
→ joe1234wu: 你這個方法跟我一開始想的一樣 只是在想有沒有辦法更快
→ joe1234wu: 掃完一次 O(n) 就找完
推 ckc1ark: 最小值更新每次O(1)*看完每個值是O(n)沒錯啊 我有誤會什
→ ckc1ark: 麼嗎
推 Thisisnotptt: 樓上的做法感覺應該沒錯，差的n-Order應該是差再一
→ Thisisnotptt: 個是直接記錄下最大值，每往前走便比較一次是否大
→ Thisisnotptt: 於最大值，若非則不處理，若是則更新最大值，所以
→ Thisisnotptt: 整個只走過一次，並不用每走一步就再用一個迴圈去
→ Thisisnotptt: 找一次最大值
→ joe1234wu: 感謝詳細解釋 那0~j-1但最小值該如何更新呢？