LeetCode.123 - 买卖股票的最佳时机 III

• LeetCode - 123. 买卖股票的最佳时机 III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路

1. 任意一天可能处于五种状态中：空仓 0、持仓 1、空仓 1、持仓 2、空仓 2
2. 某一天的操作可能有三种：买入、卖出、不操作
3. 「持仓 1」状态来源
   • 前一日「持仓 1」不操作
   • 前一日「空仓 0」买入股票
4. 「空仓 1」状态来源
   • 前一日「空仓 1」不操作
   • 前一日「持仓 1」卖出股票
5. 「持仓 2」状态来源
   • 前一日「持仓 2」不操作
   • 前一日「空仓 1」买入股票
6. 「空仓 2」状态来源
   • 前一日「空仓 2」不操作
   • 前一日「持仓 2」卖出股票
7. 分别使用 holdV1, holdV2, emptyV1, emptyV2 记录「持仓 1、空仓 1、持仓 2、空仓 2」几个状态下交易员持有的最大现金

var maxProfit = function (prices) {
  let [holdV1, holdV2, emptyV1, emptyV2] = [Number.MIN_SAFE_INTEGER, Number.MIN_SAFE_INTEGER, 0, 0]
  for (const curPrice of prices) {
    holdV1 = Math.max(holdV1, -curPrice)
    emptyV1 = Math.max(emptyV1, holdV1 + curPrice)
    holdV2 = Math.max(holdV2, emptyV1 - curPrice)
    emptyV2 = Math.max(emptyV2, holdV2 + curPrice)
  }
  return emptyV2
}