Leet Code 題目 121: Best Time to Buy and Sell Stock
題目解釋：你可以買一次股票跨琳、賣一次股票粘拾，你已經(jīng)知道該股票在每一天的價格鸵膏，請算出來只能買一次纳猪、賣一次股票陋葡，可獲得的最大利潤為何棋傍？例如：[7,1,5,3,6,4] 在 1 的時候買入救拉，6 的時候賣出，可獲得最大利潤為 5瘫拣。
Step 1: 新增一個測試用例近上，prices 長度為 2，no transaction done拂铡。
【測試代碼】prices 為 {5,4}, 因為怎麼買賣都不會賺錢壹无，所以 max profit 為 0。
【生產(chǎn)代碼】?
Step 2: hard-code 判斷前者比後者大斗锭，則回傳0。
【生產(chǎn)代碼】如果 prices[1] 比 prices[0] 小失球，回傳 0岖是。
【重構(gòu)測試代碼】?擷取方法实苞，將 assertion 行為抽取到 AssertMaxProfitShouldBe()
Step 3: 新增測試用例豺撑，prices 長度仍為 2，後者比較大黔牵，回傳差值聪轿。
【測試代碼】
【生產(chǎn)代碼】?hard-code 判斷當(dāng)後者比前者大時，回傳兩者差值猾浦，即為 max profit陆错。
Step 4: 新增測試用例金赦，prices 長度為 3, 最大值為最後一位音瓷。
【測試代碼】?預(yù)期會失敗，因為期望結(jié)果為 3夹抗，目前實現(xiàn)的生產(chǎn)代碼實際結(jié)果為 2绳慎。強(qiáng)制驅(qū)動生產(chǎn)代碼設(shè)計，當(dāng)數(shù)字長度不只 2 位時漠烧，該怎麼處理杏愤。
【生產(chǎn)代碼】?透過 Skip(1) 取得剩下的 prices, 並且取其中最大值沽甥，與目前比較的 price 取差值声邦。（仍屬 hard-code 階段）
Step 5: 新增通過的測試用例
【新增預(yù)期通過的測試代碼】?prices 為 {4,7,6} 也可以符合 remainPrices 與取 Max() 差值的需求摆舟。因為比較點仍在 prices[0] 的 4。
【新增預(yù)期通過的測試代碼】?即使 prices 長度不只是 3, 只要 prices[0] 是比較值，目前的生產(chǎn)代碼就能滿足此需求恨诱。
我的 TDD 習(xí)慣媳瞪，當(dāng) baby step 的內(nèi)容比較複雜一點且變成綠燈時，我會多寫幾個有代表性的測試案例來確保目前實現(xiàn)的生產(chǎn)代碼符合我的預(yù)期照宝。
Step 6: 新增測試用例蛇受，prices[1] < prices[0]，prices 長度為 3
【測試代碼】?強(qiáng)制驅(qū)動生產(chǎn)代碼的第一個 if block 進(jìn)行修改厕鹃，擺脫 hard-code prices[1] 的部分兢仰。因為原本生產(chǎn)代碼的實現(xiàn)會回傳 0，但這個測試案例預(yù)期回傳為 6剂碴，所以會驗證失敗把将。
【生產(chǎn)代碼】?類似 Step 4 的方式處理，只是 flag 改成 prices[1]忆矛。
【重構(gòu)】?將 if/else block 中察蹲，duplicate 的部分抽取到 if/else block 之外。
Step 7: 重構(gòu) algorithm, 改成遞迴處理
【生產(chǎn)代碼】?每一個 price 都跟剩餘的 prices[] 中的最大值做差值催训，保留最大差值即為 max profit洽议。
public class Solution
{
public int MaxProfit(int[] prices)
{
return FindMaxProfitFromNextPrice(prices[0], prices.Skip(1), 0);
}
private int FindMaxProfitFromNextPrice(int flag, IEnumerable<int> remainPrices, int lastMaxProfit)
{
if (!remainPrices.Any())
{
return lastMaxProfit;
}
var max = remainPrices.Max();
var currentMaxProfit = max - flag;
var maxProfit = Math.Max(lastMaxProfit,
currentMaxProfit);
return FindMaxProfitFromNextPrice(remainPrices.ElementAt(0), remainPrices.Skip(1), maxProfit);
}
}
到目前為止，需求所需商業(yè)邏輯已經(jīng)完整實現(xiàn)漫拭，但很遺憾的亚兄，無法通過 LeetCode 上效能的測試案例。
腦袋想了幾種常見的 algorithm 方式做調(diào)整采驻，但都還是失敗了儿捧。最後還是上網(wǎng)找了一下，才知道這一題 LeetCode 其實是 **max subarray problem **的變形題挑宠。從 wiki 中得知菲盾，可採用 Kadane's algorithm 來處理，讓時間複雜度降到 O(n)各淀。
Step 8: Kadane's algorithm 的實現(xiàn)
【生產(chǎn)代碼】?Kadane's algorithm 說明：
- 一串?dāng)?shù)列的最大差值懒鉴，其實是差值的總和（這邊的
currentSum），直到滿足第二點的條件碎浇，代表數(shù)列結(jié)束临谱。例如：{4,6,7}最大差值的7 - 4 = 3, 可以被轉(zhuǎn)成(6-4) + (7-6) = 3 - 當(dāng)
currentSum < 0時，代表截至目前為止奴璃，這一段最大總和已決定悉默。所以要 reset 為 0, 以便計算下一段的最大差值。 -
maxSum用來存放每一段的最大差值苟穆。
public class Solution
{
public int MaxProfit(int[] prices)
{
if (prices.Length < 2)
{
return 0;
}
return FindMaxProfitByKadane(prices);
}
private int FindMaxProfitByKadane(int[] prices)
{
var currentSum = 0;
var maxSum = 0;
for (int i = 1; i < prices.Length; i++)
{
currentSum = Math.Max(0, currentSum += prices[i] - prices[i - 1]); //less than 0, reset to 0
maxSum = Math.Max(maxSum, currentSum);
}
return maxSum;
}
}
通過 LeetCode 上所有測試用例
結(jié)論
練習(xí)這一題 LeetCode 抄课，我的心路歷程：
- 有趣的題目唱星，有感，看起來有點難又不會太難
- TDD 一下練手感
- 抽象跟磨，淬取出遞迴的方式
- 絞盡腦汁间聊，碰到無法突破的效能瓶頸
- 上網(wǎng)找相關(guān)解法，瞭解到針對這特殊需求的處理方式抵拘。原來這樣的需求用這樣的 algorithm 是可以巧妙解決的哎榴。多開的地圖包含：Maximum subarray problem, Kadane's algorithm, 動態(tài)規(guī)劃碍扔，其實現(xiàn)方式酸些、原理與使用場景。
說真的磕蒲，這一題如果拿來當(dāng)面試考題充尉，我覺得可以寫出「易讀且可滿足完整需求」的虛擬碼就剛好了飘言，Kadane's algorithm 的解法當(dāng)交朋友閒聊或題目補(bǔ)充就夠了。
GitHub commit history: LeetCode_121_BestTimeBuyAndSellStock
