# HW3 - Q2
###### tags: `演算法`, `109-2`

:::success
https://hackmd.io/@Cing-Chen/S1XG_XQEO
:::

## Question
**2. EXT 3-1**
In book 4.1(p.68)the author change stock buying problem into a maximum-subarray problem then use Divide-and-conquer to solve the problem，
Please proposed an O(n) Pseudo code algorithm to solve stock buying problem，which is no need of any transformation。

:::info
**Stock Buying Problem (P.68)**
You are allowed to buy one unit of stock only one time and then sell it at a later date, buying and selling after the close of trading for the day.
Your goal is to maximize your profit.
:::

## Mein Answer
### How
選舉最大的秘密就是，票多的贏、票少的輸
正如買股票也有秘密，低價買入、高價賣出，利用其中的價差賺錢

看懂這句話，這題就解完了
怎麼說？
- 先低價買入 → 買入才能賣出
- 找到高點賣出 → 在頂點的時候賣出 / 可以決定哪時候賣出
- 利用價差賺錢 → 比較哪段時間能賺最多

所以，演算法可以長這樣
- 設 預定買入、預定賣出、最大收益 三個變數，起始都是 0 或更小的數
- 爬價格陣列，如果`t=i`時比我預定買入還低 (找到更便宜的買入點)
- 把`t=i`設為預定買入點 (當然要買)
- 把`t=i+1`也就是他的下一時間設為預定賣出 (不能回到過去賣)
- 比較這樣做的話，收益會不會比較多
- 而如果`t=i`時比我預定賣出還高 (更好的價格)
- 把`t=i`設為預定賣出
- (因為我們手上有股票，可以決定咬不要留著，所以不用改預定買入點)
- 一樣比較收益化


### What

function max_profit(prices) 
{
    let maxProfit = 0
    let currentBuy = 0
    let currentSell = 0
    for(let i = 0; i < prices.length + 1; i++)
    {
        if(prices[i] < currentBuy)
        {
            currentBuy = prices[i]
            currentSell = prices[i + 1]
            if(currentSell - currentBuy > maxProfit)
                maxProfit = currentSell - currentBuy
        } 
        else if(prices[i] > currentSell)
        {
          currentSell = prices[i]
          if(currentSell - currentBuy > maxProfit)
                maxProfit = currentSell - currentBuy
        }
    return maxProfit
}

可以很簡單的看出我們只用一個迴圈爬過去。無庸置疑，複雜度是O(n)