p4.md

Problem

In chapter 4.1 (p.68), the author converts the stock buying problem into the maximum-subarray problem, then solves the problem with a divide-and-conque algorithm which takes Θ(nlogn) time. Design a O(n)-time algorithm that solves the stock buying problem without transformation.

Idea

• 要設計出O(n) 時間複雜度的方法，所以資料大概是只能在計算時到「常數遍」。
• 時間不能倒退，所以從股市價格一路向右找最大利潤。

Solution

設

• p_min 為買進的價格(初始值為第1天的價格)
• p[] 為每天的價錢,
• 最大利潤(初始值為負無限大)
• day_min 為買進日(初始值為1)
• i 為日期

for(i = 2; i <= day; i++){ //開始讀進接下來的股價
    利潤＝ p[i] – p_min
    if (利潤 > 最大利潤){
        最大利潤 = 利潤
        買進日期 = day_min
        賣出日期 = i
        買進價格 = p_min
        賣出價格 = p[i]
    }
    else if(利潤 < 0){
        p_min ＝ p[i] 
        day_min= i
    }
}