よわよわエンジニアが解くLeetcode 121. Best Time to Buy and Sell Stock

まずはブルートフォースで実装してみました

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

        min_index = 0
        min_price = 10 ** 6

        max_index = 0
        max_price = 0

        for i, price in enumerate(prices):
            if min_price > price:
                min_price = price
                min_index = i
        
        for j, price in enumerate(prices[min_index:], start=min_index):
            if max_price < price:
                max_price = price
                max_index = j
        
        return max_price - min_price

次に1回のリスト走破で解く方法を考えます
以下の例は、max_priceを保持すると過去のものも見てしまうためNG

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

        min_price = 10 ** 6
        max_price = 0
        max_profit = 0
        
        for i, price in enumerate(prices):

            if price < min_price:
                min_price = price

            if price > max_price:
                max_price = price

            profit = (max_price - min_price)
            
            if max_profit < profit:
                max_profit = profit

        return max_profit

max_priceは保持せず、最大利益だけを保持すればOK

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

        min_price = 10 ** 6
        max_profit = 0

        for price in prices:
            if price < min_price:
                min_price = price
            
            profit = price - min_price
            if profit > max_profit:
                max_profit = profit

        return max_profit