Re: [討論] 令人印象深刻的遞迴問題？
: ========================================================================
: 如果，我是說如果，不考慮 performance。
: 左買右賣，每一個價錢只有買，賣，不做動作三種可能。
: 進出場可超過一次。
: 我選擇 dfs，因為 coding 簡單容易除錯。
: 程式碼：http://paste.plurk.com/show/414602/
: 如果考慮同一個價錢可賣掉之前的股份又買進目前的價位，
: 就變得複雜許多，自行研究吧。
先考慮一下我們要不要在同一先賣再買：
(a)如果在某一天買，代表在接下來的日子裡，至少有一天的價格會超過今天
（不然一定虧錢）
(b)如果在某一天賣，代表在接下來的日子裡，價格不會更高了
（不然過幾天賣賺更多）
可以看到兩者不會同時發生，因此在這個問題中我們不用考慮同一天買＋賣
那麼問題就簡單多了，要考慮的就是：在哪幾天賣？
由(b)可知，如果在第i天賣，則i滿足：
for all j > i, prices[j] <= prices[i] (有沒有 = 應該不影響最後結果)
程式碼在此： http://codepad.org/3XhHtMWx
決定要不要買是在第 12 ~ 14 行，剩下的是算賺多少還有輸出訊息。
如果有錯誤之處還請大家幫忙指正。
(如果還要考慮手中的資本、手續費可能會很好玩)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.146.40
討論串 (同標題文章)