跳至主要內容

买卖股票的最佳时机

linwu大约 1 分钟

买卖股票的最佳时机

题目描述

给定一个数组 prices,它的第 i 个元素 prices[i] 表示某只股票在第 i 天的价格。你可以尽可能地完成更多的交易(多次买卖一支股票)。但是,你不能同时参与多笔交易(即,你必须在再次购买之前出售掉之前的股票)。

请你计算能够获得的最大利润。

解题步骤

为了计算能够获得的最大利润,我们可以使用动态规划的思想来解决问题。

  1. 定义状态:我们可以将问题转化为每一天的最优解。令 dp[i] 表示第 i 天的最大利润。

  2. 初始状态:根据题目的约束,如果只有一天的价格,那么最大利润为 0。即 dp[0] = 0

  3. 状态转移方程:对于第 i 天,我们有两种选择:买入股票或卖出股票。如果我们决定买入股票,那么最大利润为 dp[i-1] - prices[i];如果我们决定卖出股票,那么最大利润为 dp[i-1] + prices[i] - prices[i-1]。因此,状态转移方程为 dp[i] = max(dp[i-1] - prices[i], dp[i-1] + prices[i] - prices[i-1])

  4. 最终解:问题的解即为最后一天的最优解,即 dp[n-1],其中 n 是股票价格数组的长度。

下面是使用动态规划解决买卖股票的最佳时机问题的算法框架:

function maxProfit(prices) {
  const n = prices.length;
  if (n <= 1) {
    return 0;
  }

  const dp = new Array(n);
  dp[0] = 0;

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

  return dp[n - 1];
}

关注公众号

和小伙伴们一起学习

加入技术交流群

扫描二维码 备注加群