[Leetcode] 121. Best Time to Buy and Sell Stock

문제

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-100-liked

풀이

sell위치가 buy위치 이후에 와야한다는 점을 고려하여 min_price를 갱신해주면서, 선형적으로 정답을 체크했다.

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

        for price in prices:
            ans = max(ans, price - min_price) # ans 갱신(profit이 음수여도 ans초기값 0이라서 괜찮다)
            min_price = min(min_price, price) # min_price 갱신
        
        return ans

참고로 discussion을 보니, min max보다 if/else로 하는 것이 더 빠르다고 한다. 단지 2가지 숫자를 비교할 때 성능을 위해서는 if/else를 써야겠다.

cf. Kadane's Algorithm이란?
Dynamic Programming을 이용한 연속적인 부분 배열(subarray)의 최대 합을 구하는 효율적인 알고리즘