Best Time to Buy and Sell Stock with Cooldown

Problem

You are given an array prices where prices[i] is the price of a given stock on the i^th 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).

Example 1:

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

Example 2:

Input: prices = [1]
Output: 0

Constraints:

1 <= prices.length <= 5000
0 <= prices[i] <= 1000

Solution

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    const dp = [{ rest: 0, buy: -prices[0], sell: 0 }];

    for (let i = 1; i < prices.length; i++) {
        const rest =  Math.max(dp[i - 1].rest, dp[i - 1].sell); // cooldown or rest
        const buy = Math.max(dp[i - 1].buy, dp[i - 1].rest - prices[i]); // buy or hold stock
        const sell = dp[i - 1].buy + prices[i]; // sell stock
        dp.push({ rest, buy, sell });
    }

    const { rest, sell } = dp[prices.length - 1];
    return Math.max(rest, sell);
};

We will implement a DP solution. Notice dp[i] have three fields, rest, buy, and sell. Let dp[i] be the maximum profit on day i (ie. prices[0:i + 1]) by taking the action of:

On cooldown or resting when we have no stock (rest).
Buying stock or have unsold stock that we are not selling (buy).
Selling our current stock (sell).

These three cases covers all possible choices that can be made.

For the base case, if i = 0, then dp[0] = { rest: 0, buy: -prices[0], sell: 0 } since we are making 0 profits by resting, spending prices[0] amount of money by buying, and making 0 profits by selling as we have no stock.
For the recursive case (take the max for each of the scenarios):
- rest is only a valid option if we were on rest or sell directly before.
- buy is only a valid option if we were on rest or buy directly before (this ensures we respect the buying cooldown). If we were on rest before, we need to pay the cost of buying the stock (ie. prices[i]).
- sell is only a valid option if we were on buy directly before (this ensures we do not sell without having any stock). Since this is the only option, we receive the profit from selling.

Problem​

Solution​

Problem

Solution