121. Best Time to Buy and Sell Stock (ArrayDynamic Programming)

링크 - https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

이 문제는 linear하게 one pass로 풀 수 있다. 

[7,1,5,3,6,4]를 예로 들어보자. 우리는 여기서 가장 낮은 값과 가장 큰 값을 구해서 빼면 그것이 정답이다. prices를 for문으로 돌리면서, 이전 min_price보다 작으면 min_price를 업데이트하고, 아니면 ans = max(ans, p-min_price)를 통해 매번 정답을 업데이트한다.

Code

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

        for p in prices:
            if p < min_price:
                min_price = p
            else:
                ans = max(ans, p - min_price)

        return ans

Complexity

Time Complexity: O(n)

Space Complexity: O(1)