121. Best Time to Buy and Sell Stock

[fockspaces]

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.

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 <= 105 0 <= prices[i] <= 104

[fockspaces]

維護兩個變數

1. buy（當前最低買點） => min(buy, price)
2. max_profit（當前最大獲利）=> max(max_profit, price - buy) 即可得到全局最大獲利

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = INT_MAX, max_profit = 0;
        for(int price : prices) {
            max_profit = max(max_profit, price - buy);
            buy = min(buy, price);
        }
        return max_profit;
    }
};

[ZhongKuo0228]

用暴力解，但submit會失敗

var maxProfit = function(prices) {
    let max = 0;
    for(let i = 0; i < prices.length; i++){
        for(let j = i+1; j < prices.length; j++){
            let value = prices[j] - prices[i] ;
            if(value > 0 && value > max){
                max = value;
            }
        }
    }

    return max;
};

[ZhongKuo0228]

Fock 用很厲害的解法

var maxProfit = function(prices) {
    let buy = Infinity, max_profit = 0;
    for(const price of prices) {
        max_profit = Math.max(max_profit, price - buy);
        buy = Math.min(buy, price);
    }
    return max_profit;
};

//           7, 1, 5, 3, 6, 4
// buy -inf  7. 1. 1. 1. 1. 1
// pro. 0.   0. 0. 4. 4. 5. 5

// const buy = [7. 1. 1. 1. 1. 1]
// const prof = [0. 0. 4. 4. 5. 5]

[ZhongKuo0228]

python 的寫法

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #因爲不知道未來的買價多少的，所以先假設買價都是無限大，最大收益未知
        buy = float('inf') #python無限大
        max_profit = 0
        #開始購買，先更新當天的買價
        for price in prices:
            #記錄最大收益
            max_profit = max(max_profit, price - buy)
            #保留最低的買價
            buy = min(buy, price)
        return max_profit

[fockspaces]

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy, profit = float('inf'), 0
        for price in prices:
            profit = max(profit, price - buy)
            buy = min(buy, price)
        return profit

[fockspaces]

1. we should pick the lowest price to buy and highest price to sell.
2. the sell day should be after the buy day

based on this, our approach is to keep updating our profit, which might change if the difference of current holding price and current sell price larger than past profit.

we only update the buy price after we perform the transaction, ensuring that the buy price is before sell price.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy = prices[0]
        max_profit = 0
        for price in prices:
            max_profit = max(max_profit, price - buy)
            buy = min(buy, price)
        return max_profit