[LeetCode, 리트코드] Best Time to Buy and Sell Stock with Cooldown

1. Problem

 

Say you have an array for which the ith element is the price of a given stock on day i.

 

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

• You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
• After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

Input: [1,2,3,0,2]
Output: 3 
Explanation: transactions = [buy, sell, cooldown, buy, sell]

2. Solution

 

DP를 이용하여 문제를 해결할 수 있다. DP를 적용하기 전에는 부분문제에 대한 결과값을 저장할 캐쉬를 만들어야하고 각 캐쉬에 대한 정의를 명확하게 해야한다. 이 문제에서 직관적으로 3개의 캐쉬를 사용할 수 있을 수 있다.

buy[i] : 트랜잭션이 buy로 끝나는 최대 이익을 실현하는 거래 순서

sell[i] : 트랜잭션이 sell로 끝나는 최대 이익을 실현하는 거래 순서

rest[i] : 트랜잭션이 rest 즉 계속 보유하는 것으로 끝나는 최대 이익을 실현하는 거래 순서

buy[i], sell[i], rest[i]는 각각에 대하여

buy[i] = max(buy[i-1], rest[i-1] - prices)

sell[i] = max(buy[i-1] + prices, sell[i-1])

rest[i] = max(sell[i-1], buy[i-1], rest[i-1])

로 나타낼 수 있다. 이 중 buy[i] <= rest[i] <= sell[i] 를 만족하므로 위 식은 다음과 같이 된다. 

buy[i] = max(buy[i-1], sell[i-2] - prices)

sell[i] = max(buy[i-1] + prices, sell[i-1])

왜냐하면 rest[i] <= sell[i] 이므로 rest[i] = sell[i-1]이기 때문이다. max(sell[i-1], buy[i-1], rest[i-1]) = max(sell[i-1], rest[i-1]) = sell[i-1] = rest[i]

또한 buy와 sell의 부분결과값을 저장하는 배열 중 실제 사용하는 것은 i-2, i-1 부분이므로 전체 배열을 사용하는 것이 아닌 일부분만 사용하여 O(1)의 space complexity로 알고리즘을 설계할 수 있다.

3. Code

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1)
            return 0;

        int sell=0, prev_sell=0, buy=Integer.MIN_VALUE, prev_buy;

        for (int i = 0; i < prices.length; ++i) {
            prev_buy = buy;
            buy = Math.max(prev_sell - prices[i], prev_buy);
            prev_sell = sell;
            sell = Math.max(prev_buy + prices[i], prev_sell);
        }
        return sell;
    }
}