写点什么

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

用户头像
Lee Chen
关注
发布于: 2021 年 02 月 28 日
LeetCode题解:122. 买卖股票的最佳时机 II,动态规划,JavaScript,详细注释

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


解题思路:


  1. 0i - 2天进行了各种操作后,在i - 1天会有两种状态,卖出或者买入股票。

  2. i天可以做两种操作:

* 卖出:前一天买入后,今天可以卖出获得收益,就卖出。否则保持之前已卖出的状态不变。

* 买入:前一天卖出后,今天可以支付prices[i]的价格买入股票。但如果买入后,反而减少了利润,就不买了。

  1. 状态转移方程:

* 卖出: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);};
复制代码


发布于: 2021 年 02 月 28 日阅读数: 19
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:122. 买卖股票的最佳时机 II,动态规划,JavaScript,详细注释