###### tags: `Array`
<h1>
Leetcode 121. Best Time to Buy and Sell Stock
</h1>
<ol>
<li>問題描述</li>
You are given an array prices where prices[i] is the price of a given stock on the ith 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.<br><br>

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.<br>
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.

<li>Input的限制</li>
<ul>
<li>1 <= prices.length <= 10^5</li>
<li>0 <= prices[i] <= 10^4</li>
</ul>
<br>

<li>思考流程</li>
<ul>
<li>One pass</li>
要最大化利潤，首先要找高點和低點最大落差的組合；第二，買的日期不能在賣的日期之後。因為必須先買再賣才會有利潤產生，所以我們可以記錄目前碰到的最低買點，並在其後的日期皆計算與該買點的利差，更新且紀錄最大利潤數值。有沒有可能雖然買點比較高，卻最大利潤比低買點更高的情況呢 ? 如果發生了這種情況，那最大利潤的紀錄將會被保持，後面的最低買點的利潤差將不會被記錄。
<br>
<br>
所以，作法為記錄最大利潤差和最低買點，當碰到買點更低時就進行最低買點的更新，碰到較高點就計算與最低買點的利差，如果利差超過最大利潤差，就進行更新，這樣只要掃過整個 array 就可以知道最大利潤差是多少。
<br>
<br>
因為需要走過 array 一遍，所以 time complexity 是 O(n)；因為只用了 max_profit 和 min_price 進行記錄，故 space complexity 是 O(1)。
<br>
<br>
Time Complexity: O(n); Space Complexity: O(1)
<br>
<br>
</ul>
<li>測試</li>
<ul>
<li>test 1( edge case )</li>
如果 input 為 empty list，則須回報錯誤訊息。
<li>test 2( edge case )</li>
如果 list 內有元素不是數字，也須回報錯誤訊息。
<li>test 3</li>
Input: prices = [2,10,8,1,7]<br>
Output: 8
<li>test 4</li>
Input: prices = [5, 4, 3, 2]<br>
Output: 0
</ol>