[LeetCode] Python - 122. Best Time to Buy and Sell Stock II

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

Best Time to Buy and Sell Stock II - LeetCode

생각

Best Time to Buy and Sell Stock 문제와 다르게 동일날짜에 주식을 사고 다시 팔수있는 조건이 추가되었다.

이 문제도 DP로 분류되어있어서 최대 수익을 찾기위해 DFS + DP 로 접근하였는데 단순하게 생각하면 되는 문제였다.

 

먼저, 최대 수익은 싼값에 주식을 사고 비싼값에 주식을 팔면 수익이 나는 원리이다. 또한, 위의 두번째 그림에서 첫번째 날짜에 사서 두번째 날짜에 팔고, 연속해서 2일에 사고 3일에 팔고를 반복하면 1일에사서 5일에 파는 수익과 동일해진다. 즉, 하루 차이로 수익이 발생한다면 이를 모두 누적하면되는것이다

 

Python Code

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