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

链接：123.买卖股票的最佳时机III
难度：Hard
标签：数组、动态规划
简介：给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

题解 1 - typescript

• 编辑时间：2021-01-09
• 执行用时：1028ms
• 内存消耗：85.4MB
• 编程语言：typescript
• 解法介绍：动态规划计算每个状态。

function maxProfit(prices: number[]): number {
  const len = prices.length;
  if (len < 2) return 0;
  // 0 手上没，1 手上有
  // 0 完成0次交易 1 完成1次交易 2 完成两次交易
  const dp: number[][][] = new Array(len)
    .fill(0)
    .map(_ => new Array(2).fill(0).map(_ => new Array(3).fill(-Infinity)));
  [dp[0][0][0], dp[0][1][0]] = [0, -prices[0]];
  for (let i = 1; i < len; i++) {
    dp[i][0][0] = dp[i - 1][0][0];
    dp[i][0][1] = Math.max(prices[i] + dp[i - 1][1][0], dp[i - 1][0][1]);
    dp[i][0][2] = i >= 3 ? Math.max(prices[i] + dp[i - 1][1][1], dp[i - 1][0][2]) : 0;
    dp[i][1][0] = Math.max(dp[i - 1][1][0], -prices[i]);
    dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][1] - prices[i]);
    dp[i][1][2] = 0;
  }
  return Math.max(dp[len - 1][0][2], dp[len - 1][0][1]);
}

题解 2 - typescript

• 编辑时间：2021-01-09
• 执行用时：984ms
• 内存消耗：86.9MB
• 编程语言：typescript
• 解法介绍：优化题解 1。

function maxProfit(prices: number[]): number {
  const len = prices.length;
  if (len < 2) return 0;
  // 0 手上没，1 手上有
  // 0 完成0次交易 1 完成1次交易 2 完成两次交易
  const dp: number[][][] = new Array(len)
    .fill(0)
    .map(_ => new Array(2).fill(0).map(_ => new Array(3).fill(-Infinity)));
  [dp[0][0][0], dp[0][1][0]] = [0, -prices[0]];
  for (let i = 1; i < len; i++) {
    const prev = dp[i - 1];
    const prev0 = prev[0];
    const prev1 = prev[1];
    const price = prices[i];
    [dp[i][0][1], dp[i][0][2], dp[i][1][0], dp[i][1][1]] = [
      Math.max(price + prev1[0], prev0[1]),
      i >= 3 ? Math.max(price + prev1[1], prev0[2]) : 0,
      Math.max(prev1[0], -price),
      Math.max(prev1[1], prev0[1] - price),
    ];
  }
  return Math.max(dp[len - 1][0][2], dp[len - 1][0][1]);
}

题解 3 - typescript

• 编辑时间：2021-01-09
• 执行用时：1008ms
• 内存消耗：82.7MB
• 编程语言：typescript
• 解法介绍：优化题解 1。

function maxProfit(prices: number[]): number {
  const len = prices.length;
  if (len < 2) return 0;
  // 0 手上没，1 手上有
  // 0 完成0次交易 1 完成1次交易 2 完成两次交易
  const dp: number[][][] = new Array(len)
    .fill(0)
    .map(_ => new Array(2).fill(0).map(_ => new Array(3).fill(-Infinity)));
  [dp[0][0][0], dp[0][1][0]] = [0, -prices[0]];
  let [dp01, dp02, dp10, dp11] = [-Infinity, -Infinity, -prices[0], -Infinity];
  for (let i = 1; i < len; i++) {
    const price = prices[i];
    [dp01, dp02, dp10, dp11] = [
      Math.max(price + dp10, dp01),
      i >= 3 ? Math.max(price + dp11, dp02) : 0,
      Math.max(dp10, -price),
      Math.max(dp11, dp01 - price),
    ];
  }
  return Math.max(dp01, dp02);
}
// 6
console.log(maxProfit([3, 3, 5, 0, 0, 3, 1, 4]));
// 4
console.log(maxProfit([1, 2, 3, 4, 5]));
// 0
console.log(maxProfit([2, 1, 4]));

题解 4 - python

• 编辑时间：2023-10-03
• 执行用时：1924ms
• 内存消耗：80.1MB
• 编程语言：python
• 解法介绍：dp[i][j][k]表示i天j笔手上有无。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        # [i][j][k] i天j笔手上有无
        dp = [[[-inf for _ in range(2)] for _ in range(3)] for _ in range(n)]
        num0 = dp[0][0][0] = 0
        num1 = dp[0][0][1] = -prices[0]
        res = 0
        num2 = num3 = -inf
        for i in range(1, n):
            dp[i][0][0] = dp[i - 1][0][0]
            dp[i][0][1] = num0 - prices[i]
            dp[i][1][0] = num1 + prices[i]
            dp[i][1][1] = num2 - prices[i]
            dp[i][2][0] = num3 + prices[i]
            num0 = max(num0, dp[i][0][0])
            num1 = max(num1, dp[i][0][1])
            num2 = max(num2, dp[i][1][0])
            num3 = max(num3, dp[i][1][1])
            res = max(res, dp[i][1][0], dp[i][2][0])
        return res