[파이썬 알고리즘 인터뷰] 주식을 사고팔기 가장 좋은 시점

Best Time to Buy and Sell Stock - LeetCode

나의코드

def maxProfit(self, prices: List[int]) -> int:
    min_price=prices[0]
    profit=0
    for price in prices:
        min_price=min(price, min_price)
        profit = max(profit, price-min_price)
            
    return profit

최저점과 profit을 계산해 나가면서 가장 큰 profit을 찾는 방식

브루트포스로 계산

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²)의 시간복잡도로 타임아웃이 발생한다.

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

def maxProfit(self, prices: List[int]) -> int:
    min_price=sys.maxsize
    profit=0
    for price in prices:
        min_price=min(price, min_price)
        profit = max(profit, price-min_price)
            
    return profit

• sys.maxsize : 시스템 상에서 가장 큰 정수값
• float('-inf'), float('-inf') : 다음과 같은 방법으로 무한대를 지정해줄 수도 있다.

나의 풀이와 동일한 방식이다. sys.maxsize를 사용했다는 차이만 있다.