leetcode easy : Best Time to Buy and Sell Stock

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

Best Time to Buy and Sell Stock - LeetCode

 

전형적인 dp문제다.

naive하게 생각하면 O(N^2)이지만

우리가 관심있게 생각하는건 어떤 price와 과거 price 차의 최대값이다.

그러니까 과거 price는 최소값만 가지고 있으면 된다.

그러면 필요없는 계산을 줄이고 O(N)으로 풀 수 있다.

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

        minval = prices[0]

        for price in prices:
            answer = max(answer, price - minval)
            minval = min(minval, price)

        return answer