前一段時(shí)間，小灰發(fā)布了上下兩篇關(guān)于股票買賣的算法題講解，激發(fā)了很多小伙伴的興趣。

這一次，小灰把這兩篇漫畫(huà)整合在一起，并且修改了其中的一些細(xì)節(jié)錯(cuò)誤，感謝小伙伴們的指正。

—————? 第二天? —————

什么意思呢？讓我們來(lái)舉個(gè)例子，給定如下數(shù)組：

該數(shù)組對(duì)應(yīng)的股票漲跌曲線如下：

顯然，從第2天價(jià)格為1的時(shí)候買入，從第5天價(jià)格為8的時(shí)候賣出，可以獲得最大收益：

此時(shí)的最大收益是 8-1=7。

在上面這個(gè)例子中，最大值9在最小值1的前面，我們又該怎么交易？總不能讓時(shí)間倒流吧？

————————————

以下圖為例，假如我們已經(jīng)確定價(jià)格4的時(shí)候?yàn)橘u出時(shí)間點(diǎn)，那么此時(shí)最佳的買入時(shí)間點(diǎn)是哪一個(gè)呢？

我們要選擇價(jià)格4之前的區(qū)間，且必須是區(qū)間內(nèi)最小值，顯然，這個(gè)最佳的選擇是價(jià)格2的時(shí)間點(diǎn)。

第1步，初始化操作，把數(shù)組的第1個(gè)元素當(dāng)做臨時(shí)的最小價(jià)格；最大收益的初始值是0：

第2步，遍歷到第2個(gè)元素，由于2<9，所以當(dāng)前的最小價(jià)格變成了2；此時(shí)沒(méi)有必要計(jì)算差值的必要（因?yàn)榍懊娴脑乇人螅?，?dāng)前的最大收益仍然是0：

第3步，遍歷到第3個(gè)元素，由于7>2，所以當(dāng)前的最小價(jià)格仍然是2；如我們剛才所講，假設(shè)價(jià)格7為賣出點(diǎn)，對(duì)應(yīng)的最佳買入點(diǎn)是價(jià)格2，兩者差值7-2=5，5>0，所以當(dāng)前的最大收益變成了5：

第4步，遍歷到第4個(gè)元素，由于4>2，所以當(dāng)前的最小價(jià)格仍然是2；4-2=2，2<5，所以當(dāng)前的最大收益仍然是5：

第5步，遍歷到第5個(gè)元素，由于3>2，所以當(dāng)前的最小價(jià)格仍然是2；3-2=1，1<5，所以當(dāng)前的最大收益仍然是5：

以此類推，我們一直遍歷到數(shù)組末尾，此時(shí)的最小價(jià)格是1；最大收益是8-1=7：

public?class?StockProfit?{

????public?static?int?maxProfitFor1Time(int?prices[])?{
????????if(prices==null?||?prices.length==0)?{
????????????return?0;
????????}
????????int?minPrice?=?prices[0];
????????int?maxProfit?=?0;
????????for?(int?i?=?1;?i?????????????if?(prices[i]?????????????????minPrice?=?prices[i];
????????????}?else?if(prices[i]?-?minPrice?>?maxProfit){
????????????????maxProfit?=?prices[i]?-?minPrice;
????????????}
????????}
????????return?maxProfit;
????}

????public?static?void?main(String[]?args)?{
????????int[]?prices?=?{9,2,7,4,3,1,8,4};
????????System.out.println(maxProfitFor1Time(prices));
????}

}

我們以下圖這個(gè)數(shù)組為例，直觀地看一下買入賣出的時(shí)機(jī)：

在圖中，綠色的線段代表價(jià)格上漲的階段。既然買賣次數(shù)不限，那么我們完全可以在每一次低點(diǎn)都進(jìn)行買入，在每一次高點(diǎn)都進(jìn)行賣出。

這樣一來(lái)，所有綠色的部分都是我們的收益，最大總收益就是這些局部收益的加總：

（6-1）+（8-3）+（4-2）+（7-4） =?15

至于如何判斷出這些綠色上漲階段呢？很簡(jiǎn)單，我們遍歷整個(gè)數(shù)組，但凡后一個(gè)元素大于前一個(gè)元素，就代表股價(jià)處于上漲階段。

????public?int?maxProfitForAnyTime(int[]?prices)?{
????????int?maxProfit?=?0;
????????for?(int?i?=?1;?i?????????????if?(prices[i]?>?prices[i-1])
????????????????maxProfit?+=?prices[i]?-?prices[i-1];
????????}
????????return?maxProfit;
????}

我們?nèi)匀灰灾暗臄?shù)組為例：

首先，尋找到1次買賣限制下的最佳買入賣出點(diǎn)：

兩次買賣的位置是不可能交叉的，所以我們找到第1次買賣位置后，把這一對(duì)買入賣出點(diǎn)以及它們中間的元素全部剔除掉：

接下來(lái)，我們按照同樣的思路，再?gòu)氖Ｏ碌脑刂袑ふ业?次買賣的最佳買入賣出點(diǎn)：

這樣一來(lái)，我們就找到了最多2次買賣情況下的最佳選擇：

對(duì)于上圖的這個(gè)數(shù)組，如果獨(dú)立兩次求解，得到的最佳買入賣出點(diǎn)分別是【1,9】和【6,7】，最大收益是?（9-1）+（7-6）=9：

但實(shí)際上，如果選擇【1,8】和【3,9】，最大收益是（8-1）+（9-3）=13>9：

當(dāng)?shù)?次最佳買入賣出點(diǎn)確定下來(lái)，第2次買入賣出點(diǎn)的位置會(huì)有哪幾種情況呢？

情況1：第2次最佳買入賣出點(diǎn)，在第1次買入賣出點(diǎn)左側(cè)

情況2：第2次最佳買入賣出點(diǎn)，在第1次買入賣出點(diǎn)右側(cè)

情況3：第1次買入賣出區(qū)間從中間截?cái)?，重新拆分成兩次買賣

那么，如何判斷給定的股價(jià)數(shù)組屬于那種情況呢？很簡(jiǎn)單，在第1次最大買入賣出點(diǎn)確定后，我們可以比較一下哪種情況帶來(lái)的收益增量最大：

尋找左側(cè)和右側(cè)的最大漲幅比較好理解，尋找中間的最大跌幅有什么用呢？

細(xì)想一下就能知道，當(dāng)?shù)?次買賣需要被拆分開(kāi)來(lái)的時(shí)候，買賣區(qū)間內(nèi)的最大跌幅，就等同于拆分后的收益增量（類似于炒股的抄底操作）：

這樣一來(lái)，我們可以總結(jié)出下面的公式：

最大總收益 = 第1次最大收益 + Max（左側(cè)最大漲幅，中間最大跌幅，右側(cè)最大漲幅）

所謂動(dòng)態(tài)規(guī)劃，就是把復(fù)雜的問(wèn)題簡(jiǎn)化成規(guī)模較小的子問(wèn)題，再?gòu)暮?jiǎn)單的子問(wèn)題自底向上一步一步遞推，最終得到復(fù)雜問(wèn)題的最優(yōu)解。

首先，讓我們分析一下當(dāng)前這個(gè)股票買賣問(wèn)題，這個(gè)問(wèn)題要求解的是一定天數(shù)范圍內(nèi)、一定交易次數(shù)限制下的最大收益。

既然限制了股票最多買賣2次，那么股票的交易可以劃分為5個(gè)階段：

沒(méi)有買賣

第1次買入

第1次賣出

第2次買入

第2次賣出

我們把股票的交易階段設(shè)為變量m（用從0到4的數(shù)值表示），把天數(shù)范圍設(shè)為變量n。而我們求解的最大收益，受這兩個(gè)變量影響，用函數(shù)表示如下：

最大收益 = F（n，m）（n>=1，0<=m<=4）

既然函數(shù)和變量已經(jīng)確定，接下來(lái)我們就要確定動(dòng)態(tài)規(guī)劃的兩大要素：

1.問(wèn)題的初始狀態(tài)
2.問(wèn)題的狀態(tài)轉(zhuǎn)移方程式

問(wèn)題的初始狀態(tài)是什么呢？我們假定交易天數(shù)的范圍只限于第1天，也就是n=1的情況：

1.如果沒(méi)有買賣，也就是m=0時(shí)，最大收益顯然是0，也就是?F（1,0）= 0

2.如果有1次買入，也就是m=1時(shí)，相當(dāng)于憑空減去了第1天的股價(jià)，最大收益是負(fù)的當(dāng)天股價(jià)，也就是?F（1,1）=?-price[0]

3.如果有1次買出，也就是m=2時(shí)，買賣抵消（當(dāng)然，這沒(méi)有實(shí)際意義），最大收益是0，也就是?F（1,2）= 0

4.如果有2次買入，也就是m=3時(shí)，同m=1的情況，F（1,3）= -price[0]

5.如果有2次賣出，也就是m=4時(shí)，同m=2的情況，F（1,4）=?0

確定了初始狀態(tài)，我們?cè)賮?lái)看一看狀態(tài)轉(zhuǎn)移。假如天數(shù)范圍限制從n-1天增加到n天，那么最大收益會(huì)有怎樣的變化呢？

這取決于現(xiàn)在處于什么階段（是第幾次買入賣出），以及對(duì)第n天股價(jià)的操作（買入、賣出或觀望）。讓我們對(duì)各個(gè)階段情況進(jìn)行分析：

1.假如之前沒(méi)有任何買賣，而第n天仍然觀望，那么最大收益仍然是0，即?F（n，0） = 0

2.假如之前沒(méi)有任何買賣，而第n天進(jìn)行了買入，那么最大收益是負(fù)的當(dāng)天股價(jià)，即 F（n，1）=?-price[n-1]

3.假如之前有1次買入，而第n天選擇觀望，那么最大收益和之前一樣，即?F（n，1）=?F（n-1，1）

4.假如之前有1次買入，而第n天進(jìn)行了賣出，那么最大收益是第1次買入的負(fù)收益加上當(dāng)天股價(jià)，即那么?F（n，2）=?F（n-1，1）+ price[n-1]

5.假如之前有1次賣出，而第n天選擇觀望，那么最大收益和之前一樣，即?F（n，2）=?F（n-1，2）

6.假如之前有1次賣出，而第n天進(jìn)行2次買入，那么最大收益是第1次賣出收益減去當(dāng)天股價(jià)，即F（n，3）= F（n-1，2） - price[n-1]

7.假如之前有2次買入，而第n天選擇觀望，那么最大收益和之前一樣，即?F（n，3）=?F（n-1，3）

8.假如之前有2次買入，而第n天進(jìn)行了賣出，那么最大收益是第2次買入收益減去當(dāng)天股價(jià)，即F（n，4）=?F（n-1，3） +?price[n-1]

9.假如之前有2次賣出，而第n天選擇觀望（也只能觀望了），那么最大收益和之前一樣，即?F（n，4）=?F（n-1，4）

最后，我們把情況【2，3】，【4，5】，【6、7】，【8，9】合并，可以總結(jié)成下面的5個(gè)方程式：

F（n，0） = 0

F（n，1）=? max（-price[n-1]，F（n-1，1））

F（n，2）=? max（F（n-1，1）+ price[n-1]，F（n-1，2））

F（n，3）=? max（F（n-1，2）-?price[n-1]，F（n-1，3））

F（n，4）=? max（F（n-1，3）+?price[n-1]，F（n-1，4））

從后面4個(gè)方程式中，可以總結(jié)出每一個(gè)階段最大收益和上一個(gè)階段的關(guān)系：

F（n，m）?= max（F（n-1，m-1）+?price[n-1]，F(xiàn)（n-1，m））

由此我們可以得出，完整的狀態(tài)轉(zhuǎn)移方程式如下：

在表格中，不同的行代表不同天數(shù)限制下的最大收益，不同的列代表不同買賣階段的最大收益。

我們?nèi)匀焕弥袄赢?dāng)中的數(shù)組，以此為基礎(chǔ)來(lái)填充表格：

首先，我們?yōu)楸砀裉畛涑跏紶顟B(tài)：

接下來(lái)，我們開(kāi)始填充第2行數(shù)據(jù)。

沒(méi)有買賣時(shí)，最大收益一定為0，因此F（2,0）的結(jié)果是0：

根據(jù)之前的狀態(tài)轉(zhuǎn)移方程式，F(xiàn)（2,1）= max（F（1,0）-2，F(xiàn)（1,1））= max（-2，-1）= -1，所以第2行第2列的結(jié)果是-1：

F（2,2）= max（F（1,1）+2，F(xiàn)（1,2））= max（1，0）= 1，所以第2行第3列的結(jié)果是1：

F（2,3）= max（F（1,2）-2，F(xiàn)（1,3））= max（-2，-1）= -1，所以第2行第4列的結(jié)果是-1：

F（2,4）= max（F（1,3）+2，F(xiàn)（1,4））= max（1，0）= 1，所以第2行第5列的結(jié)果是1：

接下來(lái)我們繼續(xù)根據(jù)狀態(tài)轉(zhuǎn)移方程式，填充第3行的數(shù)據(jù)：

接下來(lái)填充第4行：

以此類推，我們一直填充完整個(gè)表格：

如圖所示，表格中最后一個(gè)數(shù)據(jù)13，就是全局的最大收益。

????//最大買賣次數(shù)
????private?static?int?MAX_DEAL_TIMES?=?2;

????public?static?int?maxProfitFor2Time(int[]?prices)?{
????????if(prices==null?||?prices.length==0)?{
????????????return?0;
????????}
????????//表格的最大行數(shù)
????????int?n?=?prices.length;
????????//表格的最大列數(shù)
????????int?m?=?MAX_DEAL_TIMES*2+1;
????????//使用二維數(shù)組記錄數(shù)據(jù)
????????int[][]?resultTable?=?new?int[n][m];
????????//填充初始狀態(tài)
????????resultTable[0][1]?=?-prices[0];
????????resultTable[0][3]?=?-prices[0];
????????//自底向上，填充數(shù)據(jù)
????????for(int?i=1;i????????????for(int?j=1;j????????????????if((j&1)?==?1){
????????????????????resultTable[i][j]?=?Math.max(resultTable[i-1][j],?resultTable[i-1][j-1]-prices[i]);
????????????????}else?{
????????????????????resultTable[i][j]?=?Math.max(resultTable[i-1][j],?resultTable[i-1][j-1]+prices[i]);
????????????????}
????????????}
????????}
????????//返回最終結(jié)果
????????return?resultTable[n-1][m-1];
????}

????//最大買賣次數(shù)
????private?static?int?MAX_DEAL_TIMES?=?2;

????public?static?int?maxProfitFor2TimeV2(int[]?prices)?{
????????if(prices==null?||?prices.length==0)?{
????????????return?0;
????????}
????????//表格的最大行數(shù)
????????int?n?=?prices.length;
????????//表格的最大列數(shù)
????????int?m?=?MAX_DEAL_TIMES*2+1;
????????//使用一維數(shù)組記錄數(shù)據(jù)
????????int[]?resultTable?=?new?int[m];
????????//填充初始狀態(tài)
????????resultTable[1]?=?-prices[0];
????????resultTable[3]?=?-prices[0];
????????//自底向上，填充數(shù)據(jù)
????????for(int?i=1;i????????????for(int?j=1;j????????????????if((j&1)?==?1){
????????????????????resultTable[j]?=?Math.max(resultTable[j],?resultTable[j-1]-prices[i]);
????????????????}else?{
????????????????????resultTable[j]?=?Math.max(resultTable[j],?resultTable[j-1]+prices[i]);
????????????????}
????????????}
????????}
????????//返回最終結(jié)果
????????return?resultTable[m-1];
????}

在這段代碼中，resultTable從二維數(shù)組簡(jiǎn)化成了一維數(shù)組。由于最大買賣次數(shù)是常量，所以算法的空間復(fù)雜度也從O（n）降低到了O（1）。

????public?static?int?maxProfitForKTime(int[]?prices,?int?k)?{
????????if(prices==null?||?prices.length==0?||?k<=0)?{
????????????return?0;
????????}
????????//表格的最大行數(shù)
????????int?n?=?prices.length;
????????//表格的最大列數(shù)
????????int?m?=?k*2+1;
????????//使用一維數(shù)組記錄數(shù)據(jù)
????????int[]?resultTable?=?new?int[m];
????????//填充初始狀態(tài)
????????for(int?i=1;i2)?{
????????????resultTable[i]?=?-prices[0];
????????}
????????//自底向上，填充數(shù)據(jù)
????????for(int?i=1;i????????????for(int?j=1;j????????????????if((j&1)?==?1){
????????????????????resultTable[j]?=?Math.max(resultTable[j],?resultTable[j-1]-prices[i]);
????????????????}else?{
????????????????????resultTable[j]?=?Math.max(resultTable[j],?resultTable[j-1]+prices[i]);
????????????????}
????????????}
????????}
????????//返回最終結(jié)果
????????return?resultTable[m-1];
????}

—————END—————

喜歡本文的朋友，歡迎關(guān)注公眾號(hào)?程序員小灰，收看更多精彩內(nèi)容

      

       

        

         

          

           

            

             
            
            

             點(diǎn)個(gè)[在看]，是對(duì)小灰最大的支持！