LeetCode:(Python)(Array) Best Time to Buy and Sell Stock II

題目連結: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/?envType=study-plan-v2&envId=top-interview-150

題意說明:

• 在時間範圍內可以多次買和賣，當天買當天賣也可以。
• 同時手上最多1張股票
• 最大化獲利

實作程式碼

我直覺想到的做法是，當價格下跌時，不斷修正購買價格，直到找到最低點

例如 7 -> 5 -> 3 -> 1 -> 9，購買價格就從7掉到5，一路掉到1，最後用9賣出。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy_prices = prices[0] #上一購買價格
        profit = 0

        for p in prices:
            if p < buy_prices: 
            #當價格比上一次購買價格低，代表之前不是好的買點
            #改用更低的價格作為買進價格
                buy_prices = p
            else:
            #當價格比上一次購買價格高，就即刻賣出，獲利了結
            #同時再次購買，等下一次價格更高賣出
                profit = (p - buy_prices) + profit
                buy_prices = p

        return profit   

優化程式碼

原本的想法沒有不好，也可以跑出贏過 90%的執行時間。

但仔細看邏輯會發現，其實不用紀錄購買價格，分成兩種做法即可

1. 當股價今天比昨天高，賣出，獲利增加，再買回。
2. 當股價今天比昨天低，沒有獲利，跳過。

這樣可以用更少的變數儲存。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0

        for i in range(1,len(prices)):
            if prices[i] - prices[i-1] > 0:
                profit = prices[i] - prices[i-1] + profit

        return profit