????????本次分享一道經(jīng)典的算法題，準(zhǔn)確的說是一道題的不同條件下的不同求法。這道題一共有六種情況，每種情況都是不同的解法，在leetcode上對應(yīng)六道題：

? ? ????前兩題為這個系列的基礎(chǔ)，也是引導(dǎo)之后解法思維方式的關(guān)鍵。

第一題，只能交易一次

????????第一題的題目如下：

????????在拿到題目之后，首先需要確定的是：買入股票的時候一定在賣出之前，體現(xiàn)在我們的參數(shù)上就是買入的時候的價格在數(shù)組中的序號是小于賣出的價格在數(shù)組中的序號的。

? ? ? ? 因?yàn)榇_定了上面的這個思路，所以我拿到題目后首先想到的是：我只要知道在每個位置上，在這個位置之前最小的數(shù)和這個位置之后最大的數(shù)，就可以通過差值計(jì)算拿到在該位置左右進(jìn)行買入賣出能拿到的最大利潤。

? ? ? ? 首先從實(shí)現(xiàn)上來說，這樣子解這道題肯定是沒有問題的，只需要最多進(jìn)行三次循環(huán)：正循環(huán)一次，記錄到每個位置時能買入的最低值；反著循環(huán)一次，記錄到每個位置時，在這個位置之后會出現(xiàn)的最大賣出值；再循環(huán)一次，計(jì)算每個位置上在左邊買右邊賣能賺到的最大值。簡單優(yōu)化后，可以將三次循環(huán)減少為兩次：正向掃描一次找到所有位置左邊的最小值。反著掃描的時候，在拿到該位置右邊的最大值的時候，直接與左邊的最小值求差。但即便這樣，在此題上消耗的時間最少為2N，空間最少為N（N為數(shù)組的長度，空間消耗最小為一個用來存儲到每個位置時左邊最小值的數(shù)組）。

????????其實(shí)這道題不論從時間還是空間上，都還能有很大的優(yōu)化空間：

? ? ? ? 上面我們已經(jīng)知道了，買入一定發(fā)生在賣出之前，即買入的價格在數(shù)組中的序號一定是小于賣出的價格在數(shù)組中的序號的。同時，我們希望買入的價盡可能的小，而賣出的價盡可能的高。

? ? ? ? 由“買入一定在賣出左邊”這里想到，是不是只進(jìn)行一次循環(huán)就可以了。所以可以從數(shù)組的第一個數(shù)開始向后思考：

????????我們用兩個變量來記錄兩個值，一個值是我們到目前為止碰到的最小的數(shù)（到目前為止可以買入的最低價），另一個變量用來記錄我們到目前為止已經(jīng)完成買入賣出的話可以賺到的最大值。從第一個數(shù)開始向最后循環(huán)，每碰到一個數(shù)，如果這個數(shù)比我們存的最小買入價更小，我們更新最小買入價，這個值可以在之后賣出的時候提供一個更小的買入價。如果當(dāng)前碰到的價格比現(xiàn)在存的最小買入價要大，我們就計(jì)算如果現(xiàn)在賣出可以賺到的數(shù)值，然后與我們記錄的在之前的最大差值，如果更大的話就更新。這樣在掃描了一遍之后，我們記錄差值的變量就必然會被更新成為最小買入與最大賣出的差值。python代碼實(shí)現(xiàn)如下：

第二題，不限制交易次數(shù)

? ? ? ? 第二題與第一題的區(qū)別在于，題目的限制由只能買賣一次變成了可以進(jìn)行無數(shù)次的買賣，但是同時只能有一筆交易在進(jìn)行中，即只有將之前買的賣出之后，才能進(jìn)行下一次的買入。

? ? ? ? 既然可以進(jìn)行無數(shù)次的交易，那么我們需要考慮的就是“用最少的時間和空間將所有的利潤都獲取到”。

? ? ? ? 因?yàn)樵诘谝活}中我們已經(jīng)實(shí)現(xiàn)了只掃描一次的算法，所以現(xiàn)在我們?nèi)匀辉谥粧呙枰淮蔚幕A(chǔ)上思考如何拿到所有可以賺到的差值。

? ? ? ? 當(dāng)我們掃描到位置 i 的時候，如果price[i]是大于price[i - 1]的，那么這個差值就可以作為我們賺到的。因?yàn)槲覀儾恍枰紤]交易次數(shù)的限制，所以我們一定可以通過通過交易拿到這個差值。如果price[i]小于price[i - 1]那么我們認(rèn)為在之前的交易已經(jīng)結(jié)束了，我們更新我們的買入價，之后遇到較高的價的時候，與當(dāng)前的低買入價求差。我們的宗旨是：只要在漲，就賺下差值，只要跌了，就重新開始。因?yàn)槲覀兣龅较旅孢@種情況的時候，x1+x2一定是大于x3的，所以一旦我們在掃描的時候發(fā)現(xiàn)當(dāng)前值就變小了，就開始重新算差值。

? ? ? ? 具體python實(shí)現(xiàn)如下：

第三題，最多交易兩次

? ? ? ? 第三題的限制是最多進(jìn)行兩次交易，同一時間只能有一筆交易存在。

? ? ? ? 因?yàn)閮晒P交易相對獨(dú)立，因?yàn)槲覀冇械谝活}的基礎(chǔ)，所以我們可以將這題進(jìn)行拆解：找到一個位置，在這個位置左邊完成一次交易，右邊完成一次交易，得到兩次交易的差值之和。

? ? ? ? 在第一題中，我們從提一個數(shù)開始向后掃描，掃到哪個位置就能得到一直到那個位置我們完成一次交易所能得到的最大差值。所以在此題中可以進(jìn)行正反兩次掃描，分別獲得每個位置前面完成一次交易所能得到的最大差值和后面完成一次交易能得到的最大值。然后計(jì)算所有位置上兩次交易得到的結(jié)果，取到最大值，就是此題的答案。

擴(kuò)展

? ? ? ? 通過以上三題，我們可以發(fā)現(xiàn)題目中真正限定的其實(shí)就是交易的次數(shù)。雖然三道題的實(shí)現(xiàn)過程都不一樣，但是我們是可以將三道題進(jìn)行一個共同的抽象的：

? ? ? ? 給定一個數(shù)組表示股票每天的價格，在最多完成 k 次交易的情況下如何獲利最多。

? ? ? ? 此時，我們就需要換一種思路，找到一個更通用的方法。因?yàn)楝F(xiàn)在k對于我們來說是一個變量，k表示的是最多能完成的交易次數(shù)，而不是必須要完成的交易次數(shù)。所以交易1~k次的情況我們都需要考慮。

? ??????我們定義local[i][j]為在到達(dá)第i天時最多可進(jìn)行j次交易并且最后一次交易在最后一天賣出的最大利潤，此為局部最優(yōu)。然后我們定義global[i][j]為在到達(dá)第i天時最多可進(jìn)行j次交易的最大利潤，此為全局最優(yōu)。它們的遞推式為：

? ? diff = prices[i] - prices[i - 1]

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

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

? ? ? ? 我們需要進(jìn)行兩級的循環(huán)，分別對應(yīng) i 與 j 。這樣在完成循環(huán)后，global[len(prices)][k]就是我們所要求的值。也即股票買賣的第四題。

? ? ? ? 本次只分享到這里，股票買賣的最后兩題又加入了新的額外限定條件，如果有興趣可以嘗試解答一下。