Day5 Leetcode Array系列---- Best Time to Buy and Sell Stock

本次題目 Best Time to Buy and Sell Stock by Ruby

目前有股價每日變動表，在一次買賣的條件下只考慮做多的狀況下，希望找出股票買賣獲利最大值

Input: [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.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

思考路線

1. 用之前題目的作法，設定兩個指針 (buy & sell) 由兩側往內逼近，這個想法是動態規劃 (Dynamic Programming)
2. 紀律 buy 與 sell 相減的結果，比較每次獲利，取大值
3. 如果獲利是負值就跳過
4. buy 取到的值比 sell 取到的值大， 就將 buy向右移動，反之 sell 向左移動

Coding Time

先指派好變數，獲利 (max) ，購買的時間 (buy) ，賣出的時間 (sell)

def max_profit( arr )
    max,buy,sell = [0,0,arr.length-1]
    
end

設定一個 while 迴圈來取值，如果 buy < sell 就繼續迴圈，如果獲利是正的就紀錄獲利與最大獲利值比較

def max_profit( arr )
    max,buy,sell = [0,0,arr.length-1]
    while buy < sell
        if arr[sell]-arr[buy] >= 0
            temp =  arr[sell]-arr[buy]
            
            if max < temp
                max = temp
            end
        end 
    end
end

當購買日的值比賣出日大，就把購買日往後移，反之把賣出日往前移，最後回傳獲利會大值

def max_profit( arr )
    max,buy,sell = [0,0,arr.length-1]
    while buy < sell
        if arr[sell]-arr[buy] >= 0
            temp =  arr[sell]-arr[buy]
            
            if max < temp
                max = temp
            end

        end

        if arr[buy] > arr[sell]
            buy += 1
        else
            sell -= 1
        end
    end
    max
end

今天到此為止，有任何問題請在下方留言或透過email、GitHub聯絡我，感謝閱讀

Daily kitty