122.买卖股票的最佳时机II

链接：122.买卖股票的最佳时机II
难度：Medium
标签：贪心、数组、动态规划
简介：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

题解 1 - typescript

• 编辑时间：2021-09-04
• 执行用时：76ms
• 内存消耗：40.1MB
• 编程语言：typescript
• 解法介绍：统计每个上升区间。

function maxProfit(prices: number[]): number {
  let ans = 0;
  for (let i = 1; i < prices.length; i++)
    if (prices[i] > prices[i - 1]) ans += prices[i] - prices[i - 1];
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-09-04
• 执行用时：84ms
• 内存消耗：41.2MB
• 编程语言：typescript
• 解法介绍：前缀和，减去前面前缀和的最小值。

function maxProfit(prices: number[]): number {
  const n = prices.length;
  /**
   *  0 : 买
   *  1 : 卖
   */
  const dp = new Array(n).fill(0).map(_ => new Array(2).fill(0));
  dp[0][0] = -prices[0];
  for (let i = 1; i < n; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
    dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
  }
  return dp[n - 1][1];
}

题解 3 - typescript

• 编辑时间：2020-11-08
• 执行用时：84ms
• 内存消耗：40.2MB
• 编程语言：typescript
• 解法介绍：动态规划。

function maxProfit(prices: number[]): number {
  const len = prices.length;
  let dp0 = 0,
    dp1 = -prices[0];
  for (let i = 1; i < len; i++) {
    dp0 = Math.max(dp0, dp1 + prices[i]);
    dp1 = Math.max(dp1, dp0 - prices[i]);
  }
  return dp0;
}