[Medium] 주식을 팔아 최대 이익을 얻는 날 구하기 2 - 122. Best Time to Buy and Sell Stock II

주어진 정수 배열 prices는 i번째 날의 주식 가격을 나타냅니다.

매일 주식을 사고 팔 수 있습니다. 단, 동시에 하나의 주식만 보유할 수 있습니다.

하지만 같은 날에 사고 즉시 팔 수는 있습니다.

 

얻을 수 있는 최대 이익을 구하세요.

예제 1:

입력: prices = [7,1,5,3,6,4]

출력: 7

설명:

• 2일째(가격 = 1)에 매수하고 3일째(가격 = 5)에 매도하여, 이익 = 5 - 1 = 4
• 4일째(가격 = 3)에 매수하고 5일째(가격 = 6)에 매도하여, 이익 = 6 - 3 = 3
• 총 이익은 4 + 3 = 7입니다.

예제 2:

입력: prices = [1,2,3,4,5]

출력: 4

설명:

• 1일째(가격 = 1)에 매수하고 5일째(가격 = 5)에 매도하여, 이익 = 5 - 1 = 4
• 총 이익은 4입니다.

예제 3:

입력: prices = [7,6,4,3,1]

출력: 0

설명:

• 양의 이익을 얻을 방법이 없으므로 주식을 구매하지 않아서 최대 이익은 0입니다.

제약 조건:

• 1 <= prices.length <= 3 * 104
• 0 <= prices[i] <= 104

 

풀이

 

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

 

 

last_min_price: 현재까지의 마지막 최저 주식 가격을 추적하기 위해 사용됩니다.

total_profit: 현재까지 얻을 수 있는 최대 이익을 추적하기 위해 사용됩니다.

배열을 순회하면서:

• 주식 가격이 현재의 값보다 바로 직전 값이 작은 경우, 주식을 팔고 얻은 이익을 기록합니다.
• 마지막까지 순회하면서 last_min_price가 마지막 주식 값보다 클 경우 주식을 팔아 이익을 기록합니다.

이 알고리즘은 단일 패스로 배열을 순회하므로 시간 복잡도는 O(n)이며, 공간 복잡도는 O(1)입니다.