------ 文章開始 ------


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

[複製網址] [開新視窗] [檢舉短網址] [QR條碼]

服務條款 - 加入會員(免費) - 回報問題網址 - 聯絡偶們 -

© 2025 PPT.cc