문제

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

한 번의 거래로 낼 수 있는 최대 이익을 산출하라
입력 : [7, 1, 5, 3, 6, 4]
출력 : 5
설명 : 1일 때 사서 6일 때 팔면 5의 이익을 얻는다

풀이

BruteForce로 계산

모든 경우의 수를 계산해 본다 -> O(N^2), timeout

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

        for i, price in enumerate(prices):
            for j in range(i, len(prices)):
                max_price = max(prices[j] - price, max_price)
    
        return max_price

저점과 현재 값과의 차이 계산

배열을 쭉 지나가면서 최저값을 저장하면서 현재 값과의 차이를 계산해준다
-> O(n)

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

        min_price = prices[0]
        max_price = 0

        for price in prices:
            min_price = min(min_price, price)
            max_price = max(price - min_price, max_price)

        return max_price
        

개선점 : min_price = price[0]을 sys.maxsize로 대체 가능하다