Skip to content

LeetCode题解:122. 买卖股票的最佳时机 II,动态规划,JavaScript,详细注释 #304

@chencl1986

Description

@chencl1986

原题链接:122. 买卖股票的最佳时机 II

解题思路:

  1. 0i - 2天进行了各种操作后,在i - 1天会有两种状态,卖出或者买入股票。
  2. i天可以做两种操作:
    • 卖出:前一天买入后,今天可以卖出获得收益,就卖出。否则保持之前已卖出的状态不变。
    • 买入:前一天卖出后,今天可以支付prices[i]的价格买入股票。但如果买入后,反而减少了利润,就不买了。
  3. 状态转移方程:
    • 卖出:sell = Math.max(sell, buy + prices[i]);
    • 买入:buy = Math.max(buy, lastSell - prices[i]);
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let sell = 0; // 保存当前完成卖出交易后,赚到的利润最大值,开始时没有交易,因此为0
  let buy = -prices[0]; // 保存当前完成买入交易后,赚到的利润最大值,开始时买入股票,因此为负

  for (let i = 1; i < prices.length; i++) {
    const lastSell = sell; // 缓存上一次的利润
    // 计算当前卖出后的最大利润
    sell = Math.max(
      sell, // 如果上一次已卖出,这次没有股票可卖
      buy + prices[i], // 如果上次有买入,那么这次就按当前价格卖出,获得收益
    );
    // 计算当前买入后的最大利润
    buy = Math.max(
      buy, // 上次已经买过,这次没必要再买,否则会损失收益
      lastSell - prices[i], // 如果上次卖出过,这次就买入,等待下次卖出机会
    );
  }

  // 最后一次操作后,取最终利润的最大值
  return Math.max(sell, buy);
};

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions