事實(shí)上魄眉，這個(gè)問(wèn)題可以用最大子數(shù)組來(lái)解決晰奖，把某一天的股票價(jià)格減去前一天的股票價(jià)格，求出當(dāng)天股票價(jià)格浮動(dòng)變化致盟，再加入到數(shù)組里碎税，依次類推把每一天的價(jià)格浮動(dòng)變化組合起來(lái)構(gòu)成一個(gè)數(shù)組，求出它的最大子數(shù)組即為最大收益馏锡。
如何求出一個(gè)最大子數(shù)組(最大子數(shù)組可能有多個(gè)雷蹂，求出一個(gè)即可)呢？
首先我們可以對(duì)這個(gè)數(shù)組進(jìn)行分割杯道，從中間劃開一刀(如果數(shù)組元素個(gè)素為單數(shù)匪煌，偏左偏右劃都是可以的)，那么這個(gè)最大子數(shù)組必然在這一刀的左邊党巾，右邊或者跨越了這一刀痕的中間萎庭。
OK，那么接下來(lái)我們需要求出這三種情況的最大子數(shù)組齿拂，對(duì)它們?nèi)齻€(gè)進(jìn)行比較驳规，那么如何求出左邊數(shù)組的最大子數(shù)組呢？聰明的人已經(jīng)發(fā)現(xiàn)還是和剛才的求法一樣署海，在左邊的數(shù)組的中間再劃一刀吗购！是的，所以這個(gè)算法是用遞歸來(lái)實(shí)現(xiàn)的叹侄，一刀一刀劃下去巩搏，最后會(huì)變成最簡(jiǎn)單的子問(wèn)題，得到子問(wèn)題的答案趾代，再一級(jí)一級(jí)往回返贯底，進(jìn)行比較，就可以得出最終問(wèn)題的解了。
接下來(lái)直接貼算法
附上項(xiàng)目下載地址:https://github.com/zizhouwang/GetMaxSubarray
以上所有文字圖片均摘于算法導(dǎo)論原書第3版中文完整版 高清掃描版
