原題鏈接: http://oj./problems/best-time-to-buy-and-sell-stock-iii/
這道題是Best Time to Buy and Sell Stock的擴(kuò)展，現(xiàn)在我們最多可以進(jìn)行兩次交易。我們?nèi)匀皇褂脛?dòng)態(tài)規(guī)劃來(lái)完成，事實(shí)上可以解決非常通用的情況，也就是最多進(jìn)行k次交易的情況。
這里我們先解釋最多可以進(jìn)行k次交易的算法，然后最多進(jìn)行兩次我們只需要把k取成2即可。我們還是使用“局部最優(yōu)和全局最優(yōu)解法”。我們維護(hù)兩種量，一個(gè)是當(dāng)前到達(dá)第i天可以最多進(jìn)行j次交易，最好的利潤(rùn)是多少（global[i][j]），另一個(gè)是當(dāng)前到達(dá)第i天，最多可進(jìn)行j次交易，并且最后一次交易在當(dāng)天賣出的最好的利潤(rùn)是多少（local[i][j]）。下面我們來(lái)看遞推式，全局的比較簡(jiǎn)單，

global[i][j]=max(local[i][j],global[i-1][j])，

也就是去當(dāng)前局部最好的，和過(guò)往全局最好的中大的那個(gè)（因?yàn)樽詈笠淮谓灰兹绻?dāng)前天一定在局部最好的里面，否則一定在過(guò)往全局最優(yōu)的里面）。對(duì)于局部變量的維護(hù)，遞推式是

local[i][j]=max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff)，

也就是看兩個(gè)量，第一個(gè)是全局到i-1天進(jìn)行j-1次交易，然后加上今天的交易，如果今天是賺錢的話（也就是前面只要j-1次交易，最后一次交易取當(dāng)前天），第二個(gè)量則是取local第i-1天j次交易，然后加上今天的差值（這里因?yàn)閘ocal[i-1][j]比如包含第i-1天賣出的交易，所以現(xiàn)在變成第i天賣出，并不會(huì)增加交易次數(shù)，而且這里無(wú)論diff是不是大于0都一定要加上，因?yàn)榉駝t就不滿足local[i][j]必須在最后一天賣出的條件了）。
上面的算法中對(duì)于天數(shù)需要一次掃描，而每次要對(duì)交易次數(shù)進(jìn)行遞推式求解，所以時(shí)間復(fù)雜度是O(n*k)，如果是最多進(jìn)行兩次交易，那么復(fù)雜度還是O(n)?？臻g上只需要維護(hù)當(dāng)天數(shù)據(jù)皆可以，所以是O(k)，當(dāng)k=2，則是O(1)。代碼如下：

可以看到，這里的模型是比較復(fù)雜的，主要是在遞推式中，local和global是交替求解的。不過(guò)理清思路之后，代碼是非常簡(jiǎn)練的，不禁感嘆算法真是牛逼哈，這么個(gè)復(fù)雜生活問(wèn)題幾行代碼就解決了。