Leetcode第121題到123題連續(xù)出現(xiàn)了三道買(mǎi)賣(mài)股票相關(guān)的題目，一年前的網(wǎng)易筆試和半年前的百度面試都遇到過(guò)121題，不過(guò)不用慌，看完本文，你一定能夠完美解決買(mǎi)賣(mài)股票的問(wèn)題。那么我們由易到難，依次介紹這三道題目。

best time to buy and sell stock

121題題目是這樣的：

在所有的過(guò)程中，我們只允許一次的買(mǎi)賣(mài)，基于這個(gè)問(wèn)題，我們得到了下面的兩種解法。

根據(jù)題意，我們只需要找出數(shù)組中最大的差值即可，即 max(prices[j] – prices[i]) ，i < j。

如何得到最大的差值，只需要一次遍歷即可，在遍歷的用一個(gè)變量記錄遍歷到當(dāng)前時(shí)的最小值即可。時(shí)間復(fù)雜度為O(n).

相關(guān)的實(shí)現(xiàn)代碼如下：

classSolution{publicintmaxProfit(int[]prices){if(prices==null||prices.length2){return0;}intmin=prices[0];intprofit=0;//第i天的價(jià)格可以看作是買(mǎi)入價(jià)也可以看作是賣(mài)出價(jià)for(inti=1;i//找到更低的買(mǎi)入價(jià)if(min>prices[i]){//更新買(mǎi)入價(jià)min=prices[I];}//當(dāng)天的價(jià)格不低于買(mǎi)入價(jià)else{//如果當(dāng)天買(mǎi)出的價(jià)格比之前賣(mài)出的價(jià)格高if(profit//更新賣(mài)出價(jià)profit=prices[i]-min;}}}returnprofit;}}

第二題的解法是我在面試百度的時(shí)候想到的，應(yīng)用的是求數(shù)組中和最大的連續(xù)子數(shù)組序列的思路，這種思路又被稱為Kadane's Algorithm。我們有兩個(gè)問(wèn)題：

如何轉(zhuǎn)化為求數(shù)組中的和最大的連續(xù)子序列？相鄰兩個(gè)數(shù)作差即可，這樣的話子序列的和就是我們?cè)谧有蛄虚_(kāi)始賣(mài)出股票，在子序列最后買(mǎi)回股票所能得到的收益。

那么什么是Kadane's Algorithm呢？

kadane算法利用了數(shù)學(xué)歸納法的思想。簡(jiǎn)單來(lái)講就是，隨意給你一個(gè)現(xiàn)成的數(shù)組，比如說(shuō)?2, 1, ?3, 4, ?1, 2, 1, ?5, 4，讓你求其中的最大子列和，并不是容易的事情。但如果我們能從第一個(gè)數(shù)開(kāi)始，隨著數(shù)組的擴(kuò)充，始終對(duì)其最大子列和保持跟蹤，就可以輕易的求出任意一個(gè)數(shù)組的最大子列和。換言之，長(zhǎng)度n的數(shù)組我們不會(huì)求，長(zhǎng)度為一的總能算出來(lái)吧？長(zhǎng)度為一的算出來(lái)了，二也就能算出來(lái)，二算出來(lái)了，三就能算出來(lái)，以此類(lèi)推，用這種根據(jù)i求i+1的思想，我們就能達(dá)到最終目的。

詳細(xì)的分析一下，往一個(gè)長(zhǎng)度為i的數(shù)組后面插入第i+1個(gè)數(shù)，這時(shí)，數(shù)組的最大子列只有兩種情況，要么包括第i+1個(gè)數(shù)，要么不包括第i+1個(gè)數(shù)。即：

maxsubarraum = max(以第i+1個(gè)數(shù)結(jié)尾的子列和， 不以第i+1個(gè)數(shù)結(jié)尾的子列和)。*

先計(jì)算前者，以第i+1個(gè)數(shù)結(jié)尾的子列和怎么算呢？很簡(jiǎn)單，要么它是以第i個(gè)數(shù)結(jié)尾的子列作為前綴，要么它不以之作為前綴。假設(shè)第i+1個(gè)數(shù)為x，那么：

以第i+1個(gè)數(shù)結(jié)尾的子列和 = max(x，以第i個(gè)數(shù)結(jié)尾的子列和+x) (1)。

再計(jì)算后者，也就是不以第i+1個(gè)數(shù)結(jié)尾的子列和。這啥意思呢？其實(shí)就是插入第i+1個(gè)數(shù)之前的數(shù)組的最大子列和嘛。我們的數(shù)學(xué)歸納思想也就體現(xiàn)在這里，如果你還看不明白，我們將*式改寫(xiě)：

數(shù)列長(zhǎng)度i+1的最大子列和 = max(以第i+1個(gè)數(shù)結(jié)尾的子列和， 數(shù)列長(zhǎng)度i的最大子列和)。(2)

看到了吧，無(wú)論(1)式還是(2)式，后一種情況都可以由前一種情況推出，妥妥的數(shù)學(xué)歸納。我們的算法只要從i=1開(kāi)始，一步一步按照上面的規(guī)則走下去，那么任意一個(gè)數(shù)列的最大子列和就能求出來(lái)了！

classSolution{publicintmaxProfit(int[]prices){if(prices==null||prices.length<2)return0;intmaxCur=0;intmaxSoFar=0;for(inti=1;i0,Math.max(prices[i]-prices[i-1],maxCur+prices[i]-prices[i-1]));maxSoFar=Math.max(maxCur,maxSoFar);}returnmaxSoFar;}}

這道題的描述如下：

這道題允許無(wú)限次的買(mǎi)賣(mài)，簡(jiǎn)直太簡(jiǎn)單了吧，只要后一天的價(jià)值比前一天的大，那就買(mǎi)賣(mài)唄。不忍吐槽的一道題，代碼如下：

classSolution{publicintmaxProfit(int[]prices){if(prices==null||prices.length<2)return0;intmaxProf=0;for(inti=1;iprices[i-1]?prices[i]-prices[i-1]:0);}returnmaxProf;}}

這一題還是比較難的，題目描述如下：

我們只允許最多兩次的買(mǎi)賣(mài)，這可如何是好？我們同樣提供兩種思路：

這個(gè)問(wèn)題可以轉(zhuǎn)換成Best Time to Buy and Sell Stock I問(wèn)題。

兩次股票交易的核心是可以定義一個(gè)交易點(diǎn)，在這個(gè)交易點(diǎn)之前可以做一次交易(賺的最大數(shù)目的錢(qián)為firstProf)，在這個(gè)交易點(diǎn)之后可以做一個(gè)交易(賺的最大數(shù)目的錢(qián)是secondProf)。那么要求的是max(firstProf+secondProf)。但是這個(gè)方法的時(shí)間復(fù)雜度是O(N^2)，空間復(fù)雜度是O(1)。leetcode中顯示超時(shí)。

可以使用兩次掃描的方法避免上面的雙重循環(huán)。

不同于Best Time to Buy and Sell Stock I中定義的初始狀態(tài)A[i]表示第i天賣(mài)出掙的最大數(shù)目的錢(qián)，這個(gè)更進(jìn)一步直接定義A[i]表示前i天賺的最大數(shù)目的錢(qián)。minPrice表示從第0天到第i-1天中的最低價(jià)格。

A[0]=0。（初始狀態(tài)）A[1]=max(prices[1]-prices[0],A[0])A[2]=max(prices[2]-minPrice,A[1]).....

即A[i]=max(price[i]-minPrice,A[i-1]).

另外一次掃描從數(shù)組后向前掃描，定義B[i]表示從第i天到最后一天n能賺的最大數(shù)目的錢(qián)。

maxPrice表示第i+1天到n天的最高價(jià)格。B[n]=0。（初始狀態(tài)）B[n-1]=max(maxPrice-prices[n-1],B[n])B[n-2]=max(maxPrice-prices[n-2],B[n-1]).....

即B[i]=max(maxPrice-prices[i],B[i+1])

那么以第i天為分割點(diǎn)能賺的最多數(shù)目的錢(qián)為A[i]+B[i]問(wèn)題的解為max{A[i]+B[i]}。0<=i<=n。時(shí)間復(fù)雜度是O(N)，空間復(fù)雜度是O(N)。

classSolution{publicintmaxProfit(int[]prices){if(prices==null||prices.length<2)return0;int[]asc=newint[prices.length];int[]desc=newint[prices.length];intn=prices.length;intminprice=prices[0];intmaxProf=0;asc[0]=0;for(inti=1;iasc[i]=Math.max(prices[i]-minprice,maxProf);minprice=Math.min(prices[i],minprice);maxProf=asc[i];}desc[prices.length-1]=0;maxProf=0;intmaxprice=prices[prices.length-1];for(inti=prices.length-2;i>=0;i--){desc[i]=Math.max(maxprice-prices[i],maxProf);maxprice=Math.max(maxprice,prices[i]);maxProf=desc[i];}maxProf=0;for(inti=0;iasc[i]+desc[i]);}returnmaxProf;}}

第二種解法的核心是假設(shè)手上最開(kāi)始只有0元錢(qián)，那么如果買(mǎi)入股票的價(jià)格為price，手上的錢(qián)需要減去這個(gè)price，如果賣(mài)出股票的價(jià)格為price，手上的錢(qián)需要加上這個(gè)price。

因此我們定義了4個(gè)狀態(tài)：

Buy1[i]表示前i天做第一筆交易買(mǎi)入股票后剩下的最多的錢(qián)；Sell1[i]表示前i天做第一筆交易賣(mài)出股票后剩下的最多的錢(qián)；Buy2[i]表示前i天做第二筆交易買(mǎi)入股票后剩下的最多的錢(qián)；Sell2[i]表示前i天做第二筆交易賣(mài)出股票后剩下的最多的錢(qián)；

那么假設(shè)我們?cè)诘趇天時(shí)第二次賣(mài)出股票，我們賣(mài)出股票可以獲得Buy2[i-1]+prices[i]的錢(qián)，假設(shè)在第i天前已經(jīng)完成了兩筆交易，那么我們最多的錢(qián)是Sell2[i-1]，因此Sell2[i]=max{Sell2[i-1],Buy2[i-1]+prices[I]}同樣的道理，假設(shè)我們?cè)诘趇天時(shí)第二次買(mǎi)入股票，我們手中的錢(qián)是Sell[i-1]-prices[i]，假設(shè)我們?cè)诘趇天錢(qián)已經(jīng)賣(mài)出了兩次股票，那么我們最多的錢(qián)是Buy2[i-1]，因此Buy2[i]=max{Buy2[i-1],Sell[i-1]-prices[I]}同樣的道理我們還可以得到：Sell1[i]=max{Sell[i-1],Buy1[i-1]+prices[I]}Buy1[i]=max{Buy[i-1],-prices[I]}

可以發(fā)現(xiàn)上面四個(gè)狀態(tài)都是只與前一個(gè)狀態(tài)有關(guān)，所以可以不使用數(shù)組而是使用變量來(lái)存儲(chǔ)即可。