想請教大家....
最近遇到一個問題
情境會變成
有個數列
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 當最小值 然後往右找最大
最後在看哪個最小
但是有沒有更好或是更快的方法？
感謝

掃一遍記錄目前看過的最小值 再和目前的值相減找最大?你的目標應該是找ai和aj (j>i)然後maximize(aj-ai)吧 和max min有關係嗎

對 樓上的敘述比較對 但是無法照你第一樓說的方法做

我指的是每看一個值就當aj, ai當然不意外是已經看過的(a1~j-1)最小值

你這個方法跟我一開始想的一樣 只是在想有沒有辦法更快掃完一次 O(n) 就找完

最小值更新每次O(1)*看完每個值是O(n)沒錯啊 我有誤會什麼嗎

樓上的做法感覺應該沒錯，差的n-Order應該是差再一個是直接記錄下最大值，每往前走便比較一次是否大於最大值，若非則不處理，若是則更新最大值，所以整個只走過一次，並不用每走一步就再用一個迴圈去找一次最大值

感謝詳細解釋 那0~j-1但最小值該如何更新呢？