最佳买卖股票时机含冷冻期

二 题目

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，
你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:

输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {number[]} prices
 * @return {number}
 */
const maxProfit = (prices) => {

};

根据上面的已知函数，小伙伴们可以先尝试破解本题，确定了自己的答案后再看下面代码。

三 解题思路

/**
 * @param {number[]} prices
 * @return {number}
 */
const maxProfit = (prices) => {
  const n = prices.length;
  if (!n) {
    return 0;
  }

  // f[i][0]: 手上持有股票的最大收益
  // f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
  // f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
  const f = Array.from(Array(n), () => (Array.from(Array(3), () => 0)));
  f[0][0] = -prices[0];

  for (let i = 1; i < n; i++) {
    f[i][0] = Math.max(f[i - 1][0], f[i - 1][2] - prices[i]);
    f[i][1] = f[i - 1][0] + prices[i];
    f[i][2] = Math.max(f[i - 1][1], f[i - 1][2]);
  }
  
  return Math.max(f[n - 1][1], f[n - 1][2]);
};

console.log(maxProfit(
  [1,2,3,0,2]
));

四 统计分析

本题不需要统计分析。

五 套路分析

本题暂未发现任何套路，如果有但是 jsliang 后面发现了的话，会在 GitHub 进行补充。

jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。