---
# System prepended metadata

title: "\n    Leetcode 121. Best Time to Buy and Sell Stock\n"
tags: [Array]

---

###### 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>