# Best Time to Buy and Sell Stock

###### tags: `Easy`
> [name=出題者 : 曾致銘]

## Problem
給定一個整數 `n` 和一個長度為 `n` 的整數陣列 `prices` 且 `prices[i]` 表示第 `i+1` 天的股票價格。
你需要最大化你的利潤，要求從中選擇**一天**買入，並於**未來的另一天**賣出。
印出你所能獲得的最大利潤。倘若你無法獲得利潤，印出 `0`。

### Examples
範例 1：

輸入: 6 7 1 5 3 6 4
輸出: 5
解釋: 於第 2 天買入 (價格: 1) 並於第 5 天賣出 (價格: 6)，利潤為 6-1 = 5。
注意到於 2 天買入並於第 1 天賣出是不被允許的，因為你必須先買入再賣出。

範例 2：

輸入: 5 7 6 4 3 1
輸出: 0
解釋: 在本例中，沒有任何交易發生且最大利潤為 0。

### Constraints
- $1 \le$ `prices.size()` $\le 10^5$
- $0 \le$ `prices[i]` $\le 10^4$

### Hints

### Extra Challenge
請嘗試使用動態規劃而非暴力破解來完成，也就是說，你的時間複雜度會是 $O(n)$。

## Solution

:::spoiler Description
### Approach 1: 暴力破解

#### 思路
我們需要找到陣列中兩個數字的最大差 (即最大利潤)。同時，第二個數字 (賣出價格) 要比第一個數字 (買入價格) 大。

準確地說，我們需要算出 `max(prices[j] - prices[i])` 且對任意 `i` , `j` 滿足 `j > i`。

#### 算法

// 以下省略 cin, cout，僅呈現演算法部分
// 目前為止的最大利潤
int maxProfit = 0;

for (int i = 0; i < prices.size() - 1; i++) {
    for (int j = i + 1; j < prices.size(); j++) {
        int profit = prices[j] - prices[i];
        if (profit > maxProfit) {
            maxProfit = profit;
        }
    }
}

#### 複雜度分析
- 時間複雜度: $O(n^2)$，迴圈總共執行了 $\frac{n(n - 1)}{2}$ 次。
- 空間複雜度: $O(1)$，共使用了兩個變數 `maxProfit` 和 `profit`。

### Approach 2: 動態規劃

#### 思路
我們令 $P$ 表示 `prices`，$P_i$ 表示 `prices[i]`。
我們令 $f(i)$ 表示前 $i$ 天的最小價格。
我們令 $g(i)$ 表示前 $i$ 天所能獲得的最大利潤。
那麼我們有：

- $f(0) = P_{max}$

因為在尚未開始遍歷之前，為了確保遍歷的第一個數必然會被寫入 $f$，故將 $f(0)$ 設為價格的最大可能值，對本題而言 $P_{max} = 10^4 = 10000$。

- $g(0) = 0$

同理，在尚未開始遍歷之前，為了確保遍歷的第一個利潤必然會被寫入 $g$，且題目要求若沒有辦法獲得利潤時需輸出 0，故將 $g(0)$ 設為 0。

- $f(i) = min(f(i - 1), P_i)$

為了確保最小值會被不斷更新，故每次均檢查當前價格是否低於 $f$，若是則覆寫 $f$。

- $g(i) = max(g(i - 1), P_i - f(i))$

同理，為了確保最大利潤會被不斷更新，故每次均檢查當前最有可能成為最大利潤的 $P_i - f(i)$ 是否高於 $g$，若是則覆寫 $g$。

而本題的要求即可被轉為求出 $g($`n`$)$ 的值，因此我們只需從頭遍歷 `prices` 到尾即可。
#### 算法

// 以下省略 cin, cout，僅呈現演算法部分
// 目前為止的最小價格 f(i), f(0) = P_max = 10000
int minPrice = 10000;
// 目前為止的最大利潤 g(i), g(0) = 0
int maxProfit = 0;

for (int i = 0; i < prices.size(); i++) {
    if (prices[i] < minPrice) {
        // f(i) = min(f(i - 1), p_i)
        minPrice = prices[i];
    } else if (prices[i] - minPrice > maxProfit) {
        // g(i) = max(g(i - 1), p_i - f(i))
        maxProfit = prices[i] - minPrice;
    }
}

#### 複雜度分析
- 時間複雜度: $O(n)$，迴圈只需遍歷一次。
- 空間複雜度: $O(1)$，共只使用了兩個變數。

### 完整解答

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int prices[n];
    int minPrice = 10000;
    int maxProfit = 0;
    
    for (int i = 0; i < n; i++) {
        cin >> prices[i];
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else if (prices[i] - minPrice > maxProfit) {
            maxProfit = prices[i] - minPrice;
        }
    }
    
    cout << maxProfit << endl;
}

:::

## Reference
本題目所有內容均為翻譯並修改 LeetCode 內容，且圖片，解答均為搬運。
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/