Leet Code 題目 121: Best Time to Buy and Sell Stock
題目解釋：你可以買一次股票、賣一次股票，你已經知道該股票在每一天的價格，請算出來只能買一次、賣一次股票，可獲得的最大利潤為何？例如：[7,1,5,3,6,4] 在 1 的時候買入，6 的時候賣出，可獲得最大利潤為 5。
Step 1: 新增一個測試用例，prices 長度為 2，no transaction done。
【測試代碼】prices 為 {5,4}, 因為怎麼買賣都不會賺錢，所以 max profit 為 0。
【生產代碼】
Step 2: hard-code 判斷前者比後者大，則回傳0。
【生產代碼】如果 prices[1] 比 prices[0] 小，回傳 0。
【重構測試代碼】擷取方法，將 assertion 行為抽取到 AssertMaxProfitShouldBe()
Step 3: 新增測試用例，prices 長度仍為 2，後者比較大，回傳差值。
【測試代碼】
【生產代碼】hard-code 判斷當後者比前者大時，回傳兩者差值，即為 max profit。
Step 4: 新增測試用例，prices 長度為 3, 最大值為最後一位。
【測試代碼】預期會失敗，因為期望結果為 3，目前實現的生產代碼實際結果為 2。強制驅動生產代碼設計，當數字長度不只 2 位時，該怎麼處理。
【生產代碼】透過 Skip(1) 取得剩下的 prices, 並且取其中最大值，與目前比較的 price 取差值。（仍屬 hard-code 階段）
Step 5: 新增通過的測試用例
【新增預期通過的測試代碼】prices 為 {4,7,6} 也可以符合 remainPrices 與取 Max() 差值的需求。因為比較點仍在 prices[0] 的 4。
【新增預期通過的測試代碼】即使 prices 長度不只是 3, 只要 prices[0] 是比較值，目前的生產代碼就能滿足此需求。
我的 TDD 習慣，當 baby step 的內容比較複雜一點且變成綠燈時，我會多寫幾個有代表性的測試案例來確保目前實現的生產代碼符合我的預期。
Step 6: 新增測試用例，prices[1] < prices[0]，prices 長度為 3
【測試代碼】強制驅動生產代碼的第一個 if block 進行修改，擺脫 hard-code prices[1] 的部分。因為原本生產代碼的實現會回傳 0，但這個測試案例預期回傳為 6，所以會驗證失敗。
【生產代碼】類似 Step 4 的方式處理，只是 flag 改成 prices[1]。
【重構】將 if/else block 中，duplicate 的部分抽取到 if/else block 之外。
Step 7: 重構 algorithm, 改成遞迴處理
【生產代碼】每一個 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);
}
}
到目前為止，需求所需商業邏輯已經完整實現，但很遺憾的，無法通過 LeetCode 上效能的測試案例。
腦袋想了幾種常見的 algorithm 方式做調整，但都還是失敗了。最後還是上網找了一下，才知道這一題 LeetCode 其實是 **max subarray problem **的變形題。從 wiki 中得知，可採用 Kadane's algorithm 來處理，讓時間複雜度降到 O(n)。
Step 8: Kadane's algorithm 的實現
【生產代碼】Kadane's algorithm 說明：
- 一串數列的最大差值，其實是差值的總和（這邊的
currentSum），直到滿足第二點的條件，代表數列結束。例如：{4,6,7}最大差值的7 - 4 = 3, 可以被轉成(6-4) + (7-6) = 3 - 當
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 上所有測試用例
結論
練習這一題 LeetCode ，我的心路歷程：
- 有趣的題目，有感，看起來有點難又不會太難
- TDD 一下練手感
- 抽象，淬取出遞迴的方式
- 絞盡腦汁，碰到無法突破的效能瓶頸
- 上網找相關解法，瞭解到針對這特殊需求的處理方式。原來這樣的需求用這樣的 algorithm 是可以巧妙解決的。多開的地圖包含：Maximum subarray problem, Kadane's algorithm, 動態規劃，其實現方式、原理與使用場景。
說真的，這一題如果拿來當面試考題，我覺得可以寫出「易讀且可滿足完整需求」的虛擬碼就剛好了，Kadane's algorithm 的解法當交朋友閒聊或題目補充就夠了。
GitHub commit history: LeetCode_121_BestTimeBuyAndSellStock
