double price1[] = {100, 200, 109, 300, 209};
double price2[] = {209, 300, 109, 200, 100};
觀察上面兩例，可推得以下。
在 price1，最高價為 "第四天" 且最低價為 "第一天"
換言之，最低價的時間早於最高價。所以只要把 price1 陣列從頭到尾走一遍，
分別記下最高價與最低價的時間點，則答案就出來了，不需要使用遞迴。
在 price2，最高價為 "第二天" 且最低價為 "第五天"
換言之，最高價的時間早於最低價 → 沒辦法跟 price1 一樣『直接判斷』如何獲利最大化。
每個時間點，只會有一個價格 (或者說每一天都只有一種股價)。
不可能說，300 這個最高價出現在第 N 天，然後 100 這個最低股價也出現在第 N 天。
因此最高價與最低價永遠有先後順序。
只會是「最高 > 最低」，或「最高 < 最低」兩種狀況，
我們只需要用遞迴處理「最高價早於最低價」的情況。
############################
每當「最高 < 最低」的狀況出現時，
就按先後順序，將時間點分成「前、中、後」三段：
第一天～最高價那天 (以 price2 為例： Day1 ～ Day2)
最高價的隔天～最低價的前一天 (以 price2 為例： Day3 ～ Day4)
最低價以後 (以 price2 為例： Day5～)
因為只能買一次並賣一次，所以想要獲利最大化，則購買日只能在「前、中、後」三段之內選一個。
假設購買日在前段：
則賣出日只能選 Day2，也就是「全域最高價」出現那天。且購買日只能是「前段之內的最低價」。
將此段的最大獲利記為 MaxProfitOnA。
假設購買日在後段：
則購買日只能選 Day5，也就是「全域最低價」出現那天。且賣出日只能是「後段之內的最高價」。
將此段的獲利記為 MaxProfitOnC。
以 price2 為例，因為後段只有一天，所以最佳購買方法絕對不是發生在後段，所以此時 MaxProfitOnC = 0。
假設購買日在中段：
中段也會有個最大獲利，記為 MaxProfitOnB。
當前中後三段的最大獲利都算出來了，將其互相比較，就能得知在哪一段買可以得到最大獲利。
如果只從 price2 來看，因為中段只有 Day3 跟 Day4 兩天，而且「最高 > 最低」，
所以 MaxProfitOnB 的計算很簡單，就是 200 - 109 = 91。
但如果今天不是在算 price2，而是其他的股價組合，則又需要重頭考慮在中段裡面，
是否「中段最高股價」比「中段最低股價」還要早出現。如果是，則這個中段又要重新分成三段，不斷循環...
所以中段的處理，總是可以用遞迴函數 FindMaxProfit(PriceArray, currentMaxPriceDay+1, currentMinPriceDay-1); 去算，
而這個遞迴計算結束後，一定能得到該日期段內的最大獲利買法。 |
