309. Best Time to Buy and Sell Stock with Cooldown

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).

Example 1:

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

Example 2:

Input: prices = [1]
Output: 0

Constraints:

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

Analyze

转化冷冻期的概念：当日是否可出售股票取决于上一日是否有出售股票。因此只需要观察当天与上一天之间的联系即可。

进一步抽象出以下几种状态。

1. 当日无出售，有购买，持有 stock 的最大收益
2. 当日无出售，无购买，持有 stock 的最大收益
3. 当日有出售，不持有 stock 的最大收益
4. 当日无出售，不持有 stock 的最大收益

待确认: 是否要无视购买态？

初始表达式赋值：

1. f[0][0] = -prices[0]
2. f[0][1] = -prices[0]
3. f[0][2] = 0
4. f[0][3] = 0

状态转移：

1. 当日无出售，有购买，持有 stock 的最大收益。结合下方两种情况，表达式为：f[i - 1][3] - prices[i]
   1. 上一日无出售，不持有 stock 的最大收益。表达式为：f[i - 1][3]
2. 当日无出售，无购买，持有 stock 的最大收益。结合下方两种情况，表达式为：Max{f[i - 1][0], f[i - 1][1]}
   1. 上一日无出售，有购买，持有 stock 的最大收益。表达式为：f[i - 1][0]
   2. 上一日无出售，无购买，持有 stock 的最大收益。表达式为：f[i - 1][1]
3. 当日有出售，不持有 stock 的最大收益。结合下方两种情况，表达式为：Max{f[i - 1][0], f[i - 1][1]} + prices[i]
   1. 上一日无出售，有购买，持有 stock 的最大收益。表达式为：f[i - 1][0]
   2. 上一日无出售，无购买，持有 stock 的最大收益。表达式为：f[i - 1][1]
4. 当日无出售，不持有 stock 的最大收益。结合下方两种情况，表达式为：Max{f[i - 1][3], f[i - 1][2]}
   1. 上一日无出售，不持有 stock 的最大收益。表达式为：f[i - 1][3]
   2. 上一日有出售，不持有 stock 的最大收益。表达式为：f[i - 1][2]

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
  const arr = [[-prices[0], -prices[0], 0, 0]]

  for (let i = 1; i < prices.length; i++) {
    arr[i] = [
      arr[i - 1][3] - prices[i],
      Math.max(arr[i - 1][0], arr[i - 1][1]),
      Math.max(arr[i - 1][0], arr[i - 1][1]) + prices[i],
      Math.max(arr[i - 1][3], arr[i - 1][2]),
    ]
    console.log(`arr[${i}]`, arr[i])
  }

  const lastDay = arr[prices.length - 1]
  return Math.max(lastDay[1], lastDay[2], lastDay[3])
}