前一段時間，小灰發(fā)布了上下兩篇關(guān)于股票買賣的算法題講解，激發(fā)了很多小伙伴的興趣。
這一次，小灰把這兩篇漫畫整合在一起，并且修改了其中的一些細(xì)節(jié)錯誤，感謝小伙伴們的指正。
—————? 第二天? —————
什么意思呢？讓我們來舉個例子，給定如下數(shù)組：
該數(shù)組對應(yīng)的股票漲跌曲線如下：
顯然，從第2天價格為1的時候買入，從第5天價格為8的時候賣出，可以獲得最大收益：
此時的最大收益是 8-1=7。
在上面這個例子中，最大值9在最小值1的前面，我們又該怎么交易？總不能讓時間倒流吧？
————————————
以下圖為例，假如我們已經(jīng)確定價格4的時候為賣出時間點，那么此時最佳的買入時間點是哪一個呢？
我們要選擇價格4之前的區(qū)間，且必須是區(qū)間內(nèi)最小值，顯然，這個最佳的選擇是價格2的時間點。
第1步，初始化操作，把數(shù)組的第1個元素當(dāng)做臨時的最小價格；最大收益的初始值是0：
第2步，遍歷到第2個元素，由于2<9，所以當(dāng)前的最小價格變成了2；此時沒有必要計算差值的必要（因為前面的元素比它大），當(dāng)前的最大收益仍然是0：
第3步，遍歷到第3個元素，由于7>2，所以當(dāng)前的最小價格仍然是2；如我們剛才所講，假設(shè)價格7為賣出點，對應(yīng)的最佳買入點是價格2，兩者差值7-2=5，5>0，所以當(dāng)前的最大收益變成了5：
第4步，遍歷到第4個元素，由于4>2，所以當(dāng)前的最小價格仍然是2；4-2=2，2<5，所以當(dāng)前的最大收益仍然是5：
第5步，遍歷到第5個元素，由于3>2，所以當(dāng)前的最小價格仍然是2；3-2=1，1<5，所以當(dāng)前的最大收益仍然是5：
以此類推，我們一直遍歷到數(shù)組末尾，此時的最小價格是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));
????}
}我們以下圖這個數(shù)組為例，直觀地看一下買入賣出的時機(jī)：
在圖中，綠色的線段代表價格上漲的階段。既然買賣次數(shù)不限，那么我們完全可以在每一次低點都進(jìn)行買入，在每一次高點都進(jìn)行賣出。
這樣一來，所有綠色的部分都是我們的收益，最大總收益就是這些局部收益的加總：
（6-1）+（8-3）+（4-2）+（7-4） =?15
至于如何判斷出這些綠色上漲階段呢？很簡單，我們遍歷整個數(shù)組，但凡后一個元素大于前一個元素，就代表股價處于上漲階段。
????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次買賣限制下的最佳買入賣出點：
兩次買賣的位置是不可能交叉的，所以我們找到第1次買賣位置后，把這一對買入賣出點以及它們中間的元素全部剔除掉：
接下來，我們按照同樣的思路，再從剩下的元素中尋找第2次買賣的最佳買入賣出點：
這樣一來，我們就找到了最多2次買賣情況下的最佳選擇：
對于上圖的這個數(shù)組，如果獨立兩次求解，得到的最佳買入賣出點分別是【1,9】和【6,7】，最大收益是?（9-1）+（7-6）=9：
但實際上，如果選擇【1,8】和【3,9】，最大收益是（8-1）+（9-3）=13>9：
當(dāng)?shù)?次最佳買入賣出點確定下來，第2次買入賣出點的位置會有哪幾種情況呢？
情況1：第2次最佳買入賣出點，在第1次買入賣出點左側(cè)
情況2：第2次最佳買入賣出點，在第1次買入賣出點右側(cè)
情況3：第1次買入賣出區(qū)間從中間截斷，重新拆分成兩次買賣
那么，如何判斷給定的股價數(shù)組屬于那種情況呢？很簡單，在第1次最大買入賣出點確定后，我們可以比較一下哪種情況帶來的收益增量最大：
尋找左側(cè)和右側(cè)的最大漲幅比較好理解，尋找中間的最大跌幅有什么用呢？
細(xì)想一下就能知道，當(dāng)?shù)?次買賣需要被拆分開來的時候，買賣區(qū)間內(nèi)的最大跌幅，就等同于拆分后的收益增量（類似于炒股的抄底操作）：
這樣一來，我們可以總結(jié)出下面的公式：
最大總收益 = 第1次最大收益 + Max（左側(cè)最大漲幅，中間最大跌幅，右側(cè)最大漲幅）
所謂動態(tài)規(guī)劃，就是把復(fù)雜的問題簡化成規(guī)模較小的子問題，再從簡單的子問題自底向上一步一步遞推，最終得到復(fù)雜問題的最優(yōu)解。
首先，讓我們分析一下當(dāng)前這個股票買賣問題，這個問題要求解的是一定天數(shù)范圍內(nèi)、一定交易次數(shù)限制下的最大收益。
既然限制了股票最多買賣2次，那么股票的交易可以劃分為5個階段：
沒有買賣
第1次買入
第1次賣出
第2次買入
第2次賣出
我們把股票的交易階段設(shè)為變量m（用從0到4的數(shù)值表示），把天數(shù)范圍設(shè)為變量n。而我們求解的最大收益，受這兩個變量影響，用函數(shù)表示如下：
最大收益 = F（n，m）（n>=1，0<=m<=4）
既然函數(shù)和變量已經(jīng)確定，接下來我們就要確定動態(tài)規(guī)劃的兩大要素：
1.問題的初始狀態(tài)
2.問題的狀態(tài)轉(zhuǎn)移方程式
問題的初始狀態(tài)是什么呢？我們假定交易天數(shù)的范圍只限于第1天，也就是n=1的情況：
1.如果沒有買賣，也就是m=0時，最大收益顯然是0，也就是?F（1,0）= 0
2.如果有1次買入，也就是m=1時，相當(dāng)于憑空減去了第1天的股價，最大收益是負(fù)的當(dāng)天股價，也就是?F（1,1）=?-price[0]
3.如果有1次買出，也就是m=2時，買賣抵消（當(dāng)然，這沒有實際意義），最大收益是0，也就是?F（1,2）= 0
4.如果有2次買入，也就是m=3時，同m=1的情況，F（1,3）= -price[0]
5.如果有2次賣出，也就是m=4時，同m=2的情況，F（1,4）=?0
確定了初始狀態(tài)，我們再來看一看狀態(tài)轉(zhuǎn)移。假如天數(shù)范圍限制從n-1天增加到n天，那么最大收益會有怎樣的變化呢？
這取決于現(xiàn)在處于什么階段（是第幾次買入賣出），以及對第n天股價的操作（買入、賣出或觀望）。讓我們對各個階段情況進(jìn)行分析：
1.假如之前沒有任何買賣，而第n天仍然觀望，那么最大收益仍然是0，即?F（n，0） = 0
2.假如之前沒有任何買賣，而第n天進(jìn)行了買入，那么最大收益是負(fù)的當(dāng)天股價，即 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)天股價，即那么?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)天股價，即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)天股價，即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個方程式：
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個方程式中，可以總結(jié)出每一個階段最大收益和上一個階段的關(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ǔ)來填充表格：
首先，我們?yōu)楸砀裉畛涑跏紶顟B(tài)：
接下來，我們開始填充第2行數(shù)據(jù)。
沒有買賣時，最大收益一定為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：
接下來我們繼續(xù)根據(jù)狀態(tài)轉(zhuǎn)移方程式，填充第3行的數(shù)據(jù)：
接下來填充第4行：
以此類推，我們一直填充完整個表格：
如圖所示，表格中最后一個數(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ù)組簡化成了一維數(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)注公眾號?程序員小灰，收看更多精彩內(nèi)容
點個[在看]，是對小灰最大的支持！
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺僅提供信息存儲服務(wù)。文章僅代表作者個人觀點，不代表本平臺立場，如有問題，請聯(lián)系我們，謝謝！
下載文檔
