LeetCode Js-121. Best Time to Buy and Sell Stock

    AllenLi
    LeetCode Js-Optimization

    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.

    給予一個價格陣列，且為每一天對應的股票價格。
你希望透過選擇一天購買股票，同時在未來的一天出售該股票，以便獲得最大的利潤。
回傳在此交易中的最大利潤，如無法獲得任何利潤，則回傳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.

    Solution:
    1. 設定 min 為最大值，且起始的 profit 為 0。
    2. 依序將 prices 陣列中的售價進行比對
    3. 抓出售價中的最小值，更新為 min，否則略過。
    4. 更新「當前的利潤」為當前陣列中的售價減去 min，此為利潤。
    5. 如果「當前的利潤」出現最大值，則更新為 profit。
    6. 最終回傳最大的 profit。

    Code:

    var maxProfit = function(prices: number[]): number {
    let min: number = Number.MAX_SAFE_INTEGER
    let profit: number = 0

    for (let i = 0; i < prices.length; i++) {
        if (prices[i] < min) min = prices[i]

        let currentProfit = prices[i] - min
        if (currentProfit > profit) profit = currentProfit
    }
    return profit;
};

    FlowChart:
    Example 1

    Input: prices = [7,1,5,3,6,4]

step.1
i = 0
prices[0] < min //7 < Max
min = prices[0] //min = 7
currentProfit = prices[0] - min //7 - 7 = 0
currentProfit > profit //0

step.2
i = 1
prices[1] < min //1 < 7
min = prices[1] //min = 1
currentProfit = prices[1] - min //1 - 1 = 0
currentProfit > profit //0

step.3
i = 2
prices[2] < min //5 > 1
currentProfit = prices[2] - min //5 - 1 = 4
currentProfit > profit //4 > 0
profit = currentProfit //4

step.4
i = 3
prices[3] < min //3 > 1
currentProfit = prices[3] - min //3 - 1 = 2
currentProfit > profit //2 < 4


step.5
i = 4
prices[4] < min //6 > 1
currentProfit = prices[4] - min //6 - 1 = 5
currentProfit > profit //5 > 4
profit = currentProfit //5

step.6
i = 5
prices[5] < min //4 > 1
currentProfit = prices[5] - min //4 - 1 = 3 
currentProfit > profit //3 < 5

return profit //5

    Example 2

    Input: prices = [7,6,4,3,1]

step.1
i = 0
prices[0] < min //7 < Max
min = prices //7
currentProfit = prices[0] - min //7 - 7 = 0
currentProfit > profit //0

step.2
i = 1
prices[1] < min //6 < 7
min = prices //6
currentProfit = prices[1] - min //6 - 6 = 0
currentProfit > profit //0

step.3
i = 2
prices[2] < min //4 < 6
min = prices //4
currentProfit = prices[2] - min //4 - 4 = 0
currentProfit > profit //0

step.4
i = 3
prices[3] < min //3 < 4
min = prices //3
currentProfit = prices[3] - min //3 - 3 = 0
currentProfit > profit //0

step.5
i = 4
prices[4] < min //1 < 3
min = prices //1
currentProfit = prices[4] - min //1 - 1 = 0
currentProfit > profit //0

return profit //0

    Number.MAX_SAFE_INTEGER

    Number.MAX_SAFE_INTEGER：JavaScript中最大的安全整數(maximum sage integer) //(2^53 -1)

    Related Posts