# 121.Best Time to Buy and Sell Stock <span class="tag" data-diff="easy" />
{%hackmd RN5D4nggQRO8wzNqxuvlNw %}

## 題目
You are given an array `prices` where `prices[i]` is the price of a given stock on the $i^{th}$ day.

You want to maximize your profit by choosing a **single day** to buy one stock and choosing a **different day in the future** to sell that stock.

Return *the maximum profit you can achieve from this transaction*. If you cannot achieve any profit, return `0`.

### Example 1:

> **Input**: prices = [7,1,5,3,6,4]
**Output**: 5
**Explanation**: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

### Example 2:

> **Input**: prices = [7,6,4,3,1]
**Output**: 0
**Explanation**: In this case, no transactions are done and the max profit = 0.

### Constraints:

- 1 <= prices.length <= $10^5$
- 0 <= prices[i] <= $10^4$

## 思路
這題其實是在面試台積時遇到的白板題，面試官看著我做所以很緊張XDD
一開始看到Easy的時候還想說應該穩了，結果...

最原始的想法是採暴力解，loop過每一個item，並在剩下的元素中找最大值與他比較，來決定是否更新當前的`maxProfit`

function maxProfit(prices: number[]): number {
    let maxProfit: number = -1;

    for (let i = 0; i < prices.length; i ++) {
        const max = Math.max(...prices.slice(i + 1));
        const profit = max - prices[i];
        maxProfit = Math.max(maxProfit, profit);
    }

    return Math.max(maxProfit, 0);    
};

一開始還抱著僥倖的心態想說是easy應該怎麼寫只要答案對都可以過吧!結果就是慘紅的TLE，而且還在面試當中好丟臉>///<

還好面試官人很好(?)的說沒關係，暴力解也是一個方法...

總之，分析一下上面的code，就可以知道他的時間複雜度足足有 $O(n^2)$ 雖然不確定JS是怎麼實作`Math.max`的function，但考慮到這是一個沒有sorted的array，應該多少還是要 $O(n)$ 的時間吧...這就是一個快速好懂有用，但效率極差的程式。而要如何優化，答案也很簡單，就是鼎鼎大名的**Dynamic Programming**!

說實話我覺得一題Easy的題目要用到DP實在是太超過了QQ

### Dynamic Programming
> 動態規劃(Dynamic Programming)採用「以空間換取時間」的策略，將計算過的結果記錄在table中，來**避免重複計算子問題**，採**bottom up**的方式進行運算。

以費氏數列(Fabonacci)來看，要求 $F_5$ 的值，如果採Top-Down的算法：

graph{
    rankdir="LR";
    node [color=black,shape=circle];
    F3_1[label="F3",color="red"];
    F3_2[label="F3",color="red"];
    F2_1[label="F2",color="blue"];
    F2_2[label="F2",color="blue"];
    F2_3[label="F2",color="blue"];
    F1_1[label="F1",color="orange"];
    F1_2[label="F1",color="orange"];
    F1_3[label="F1",color="orange"];
    F1_4[label="F1",color="orange"];
    F1_5[label="F1",color="orange"];
    F0_1[label="F0",color="orange"];
    F0_2[label="F0",color="orange"];
    F0_3[label="F0",color="orange"];
    
    F5 -- F4;
    F5 -- F3_1;
    F4 -- F3_2;
    F4 -- F2_3;
    F3_1 -- F2_1;
    F3_1 -- F1_1;
    F3_2 -- F2_2;
    F3_2 -- F1_2;
    F2_1 -- F1_3;
    F2_1 -- F0_1;
    F2_2 -- F1_4;
    F2_2 -- F0_2;
    F2_3 -- F1_5;
    F2_3 -- F0_3;
    
    
}

會發現 $F_3$ 與 $F_2$ 都被計算了1次以上，但這個計算是可以被記錄的sub-problem，以下是改用bottom-up的計算方法：

| n |0|1|2|3|4|5|
| - |-|-|-|-|-|-|
|$F_n$|0|1|1|2|3|5|

將每次計算的結果存起來，在後續要使用時就可以直接調用，無須重複計算，大大提升了效率。

### DP設計流程
1. 觀察問題
2. 拆解為optimal substructure，一個問題的最佳解要如何用其sub-problem構成
3. 改寫為recurrsive
4. 用bottom up寫出DP Algorithm

### 開始設計
根據上面的定義，要設計出DP Algorithm需要幾個要素：
- bottom-up
- 由sub problem組成的optimal solution
- 記住之前算過的結果

但此題並未用到上述的第二點，僅需要用bottom-up的觀念即可完成(這麼看來說他是easy好像也沒有不對)。

用bottom-up來看，最開始(`n=2`)我們只有開頭的兩天，這時如果`prices[1] > prices[0]`則`maxProfit`為兩者相減，否則回傳0。當再多一天時，會需要考慮以下情況：

- 由於最大利潤一定是由至今為止的最小值算出來的，如果當前的price比至今為止的最小值還小，則需要將其記錄在`memorizedMin`中
- 如果當前的price比至今為止的最小值大，則他有可能產生最大利潤，故根據他產生的利潤去更新`maxProfit`

function maxProfit(prices: number[]): number {
    let maxProfit: number = 0;
    let memorizedMin = prices[0];

    for (let i = 1; i < prices.length; i ++) {
        const current = prices[i];
        if (current < memorizedMin) memorizedMin = current;
        if (current > memorizedMin) {
            maxProfit = Math.max(current - memorizedMin, maxProfit);
        }
    }

    return maxProfit;
};