[LEETCODE] 309. Best Time to Buy and Sell Stock with Cooldown 풀이

#Problem

309. Best Time to Buy and Sell Stock with Cooldown

#Approach

3가지 상태가 존재하며, 이는 다음과 같이 표현할 수 있습니다:

따라서 이 문제에는 상태 전이를 표현하는 dynamic programming 접근법을 사용할 수 있습니다.

• holding[i] = max( holding[i-1] , notHolding[i-1] - prices[i])
• notHolding[i] = max( notHolding[i-1] , cooldown[i-1] )
• cooldown[i] = holding[i-1] + prices[i]

base case를 초기화하는 것은 어렵지 않습니다,

• holding[0] = -prices[0]
• notHolding[0] = 0
• cooldown[0] = $-\infty$

최종 정답은 $\max(cooldown[n-1], notHolding[n-1])$입니다.

Note
공간 복잡도를 $O(1)$로 최적화할 수 있습니다. 아래 구현이 이를 수행합니다.

#Code

typedef vector<int> vi;

class Solution {
private:
    const int NEG_INF= -1e7;
public:
    int maxProfit(vi &prices) {
        int n= prices.size(), holding= -prices[0], notHolding= 0, cooldown= NEG_INF;
        for (int i=1; i < n; ++i) {
            int prevHolding= holding;
            holding= max(holding, notHolding-prices[i]);
            notHolding= max(notHolding, cooldown);
            cooldown= prevHolding+prices[i];
        }
        return max(cooldown, notHolding);
    }
};

#Complexity

• Time: $O(n)$
• Space: $O(n)$