LeetCode - 309. Best Time to Buy and Sell Stock with Cooldown (JavaScript)

Medium, DP

RunTime : 57 ms / Memory : 50.80 MB

문제

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

• After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

풀이

프로그래머스에서 비슷한 유형을 접했던 것 같은데, 당시에는 스택으로 해결했었다.
하지만 cooldown이 있어 단순히 스택으로만 해결할 수 있는 것 같진 않았고, GPT의 도움을 받아 해결했다.

1. 3개의 배열을 만든다.
   주식을 들고있을 때, 주식을 팔았을 때, cooldown 일 때
2. 각 날짜에 대해 당일의 이득을 최대로 취할 수 있게 시도한다.
3. 마지막날에 팔거나, 그 전에 팔아 마지막날 cooldown일 때를 비교해 Max값을 리턴한다.

var maxProfit = function(prices) {
    if(prices.length === 1){
        return 0;
    }
    const k = prices.length;
    
    let hold = new Array(k).fill(0);
    // i 번째 날 주식을 가지고 있는 상태에서의 이익
    let sell = new Array(k).fill(0);
    // i 번째 날 주식을 판 상태에서의 이익
    let rest = new Array(k).fill(0);
    // i 번째 날 쉼

    hold[0] = -prices[0]; // 첫 주식 샀다 가정
    
    for(let i = 1; i < k; i++){
        hold[i] = Math.max(hold[i - 1], rest[i - 1] - prices[i]);
        // 이전 날에 주식을 갖고있었거나, 쉬고 있던 상태에서 새롭게 주식 구매
        sell[i] = hold[i - 1] + prices[i];
        // 이전날의 값과 오늘 값의 차익 = 매매
        rest[i] = Math.max(rest[i - 1], sell[i - 1]);
    }
    return Math.max(sell[k - 1], rest[k - 1]);
};