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); 去算,
而這個遞迴計算結束後,一定能得到該日期段內的最大獲利買法。 |