121. Best Time to Buy and Sell Stock

My solution

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        result = 0
        
        for i in range(len(prices)):
            
            for j in range(i + 1, len(prices)):
                
                if prices[j] - prices[i] > result:
                    result = prices[j] - prices[i]
        
        return result

• for문을 중첩해서 써서 배열 안에 있는 숫자의 차이를 검사하는 브루트포스 풀이 방법으로 풀었지만 runtime이 초과되어 통과되진 못하였다.

시각화 작업을 통한 풀이

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        min_price = sys.maxsize
        
        # 최솟값과 최댓값을 계속 갱신
        for price in prices:
            min_price = min(min_price, price)
            profit = max(profit, price - min_price)
            
        return profit

runtime : 68 ms

• 그래프를 그려서 시각화를 해본 뒤, 다시한번 문제를 들여다 보니까 엇떻게 풀어야할지 명확해졌다.
• 포인터가 우측으로 이동하면서 저점은 계속 갱신하고, 저점을 기준으로 가격차이 계산하여 최댓값을 계속 갱신하는 방법으로 풀이한 방법이다.

서적 파이썬 알고리즘 인터뷰 - 박상길 을 참고하였습니다.