309.best-time-to-buy-and-sell-stock-with-cooldown.md

309. Best Time to Buy and Sell Stock with Cooldown

fun maxProfit(prices: IntArray): Int {
    val dp = Array(prices.size) { IntArray(2) }
    dp[0][0] = 0
    // This is the first base case of dp[i][1]
    dp[0][1] = -prices[0]
    for (day in 1 until prices.size) {
        dp[day][0] = max(dp[day - 1][0], dp[day - 1][1] + prices[day])

        // We have to wait one day to buy, so the max profit on day `i` to buy comes from day `i - 2`.
        if (day >= 2) {
            dp[day][1] = max(dp[day - 1][1], dp[day - 2][0] - prices[day])
        } else {
            // This is the second base case of dp[i][1]
            dp[day][1] = max(dp[day - 1][1], -prices[day])
        }
    }
    return dp[prices.size - 1][0]
}