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

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

第一題，只能交易一次

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

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

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

? ? ? ? 首先從實(shí)現(xiàn)上來說悉尾，這樣子解這道題肯定是沒有問題的，只需要最多進(jìn)行三次循環(huán)：正循環(huán)一次挫酿，記錄到每個位置時能買入的最低值构眯；反著循環(huán)一次，記錄到每個位置時早龟，在這個位置之后會出現(xiàn)的最大賣出值惫霸；再循環(huán)一次，計算每個位置上在左邊買右邊賣能賺到的最大值葱弟。簡單優(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)在存的最小買入價要大讼育，我們就計算如果現(xiàn)在賣出可以賺到的數(shù)值帐姻，然后與我們記錄的在之前的最大差值，如果更大的話就更新奶段。這樣在掃描了一遍之后卖宠，我們記錄差值的變量就必然會被更新成為最小買入與最大賣出的差值。python代碼實(shí)現(xiàn)如下：

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

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

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

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

? ? ? ? 當(dāng)我們掃描到位置 i 的時候因俐，如果price[i]是大于price[i - 1]的，那么這個差值就可以作為我們賺到的周偎。因為我們不需要考慮交易次數(shù)的限制抹剩，所以我們一定可以通過通過交易拿到這個差值。如果price[i]小于price[i - 1]那么我們認(rèn)為在之前的交易已經(jīng)結(jié)束了蓉坎，我們更新我們的買入價澳眷，之后遇到較高的價的時候，與當(dāng)前的低買入價求差蛉艾。我們的宗旨是：只要在漲钳踊，就賺下差值衷敌，只要跌了，就重新開始拓瞪。因為我們碰到下面這種情況的時候缴罗，x1+x2一定是大于x3的，所以一旦我們在掃描的時候發(fā)現(xiàn)當(dāng)前值就變小了祭埂，就開始重新算差值瞒爬。

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

第三題，最多交易兩次

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

? ? ? ? 因為兩筆交易相對獨(dú)立，因為我們有第一題的基礎(chǔ)航罗，所以我們可以將這題進(jìn)行拆解：找到一個位置禀横，在這個位置左邊完成一次交易，右邊完成一次交易粥血，得到兩次交易的差值之和柏锄。

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

擴(kuò)展

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

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

? ? ? ? 此時上祈，我們就需要換一種思路培遵，找到一個更通用的方法。因為現(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]就是我們所要求的值。也即股票買賣的第四題蛉迹。

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