122. Best Time to Buy and Sell Stock II (Array, Dynamic Programming, Greedy)

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

난이도 - Medium

Intuition

우리는 이전 가격중 가장 낮은 가격을 추적하면서 가격이 오를때마다 답을 더하는식으로 문제를 풀 수 있다.

Code

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

        if len(prices) == 1:
            return ans

        prev_price = prices[0]
        for i in range(1, len(prices)):
            if prev_price < prices[i]:
                ans += (prices[i] - prev_price)
                prev_price = prices[i]
            else:
                prev_price = min(prev_price, prices[i])
        return ans

Complexity

Time Complexity: O(n)

Space Complexity: O(1)