• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

剑指 Offer 63. 股票的最大利润

开发技术 开发技术 6天前 4次浏览

剑指 Offer 63. 股票的最大利润

题目描述:

假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?

剑指 Offer 63. 股票的最大利润

分析:本质就是求prices[i]和prices[0],prices[1],…,prices[i-1]差值的最大值(i=0,…,prices.length-1)。

1. 可以使用动态规划:

  用dp[i]表示以prices[i]结尾的最大利润,状态转移方程可以表示为:dp[i]=max[dp[i-1],prices[i]-min(prices[0], prices[1], …, prices[i-1])];初始状态dp[0]=0

2. 改进:

  • 动态规划里面求最少值的步骤里有重复计算,可以优化一下。
  • 变量min保存前i个值的最小值,max保存最大差值

代码:

 1 /**
 2  * @param {number[]} prices
 3  * @return {number}
 4  */
 5 var maxProfit = function(prices) {
 6     var min=prices[0],max=0;
 7     for(let i=1;i<prices.length;i++){
 8         min=Math.min(min,prices[i]);
 9         max=Math.max(max,prices[i]-min)
10     }
11     return max
12 };

 


程序员灯塔
转载请注明原文链接:剑指 Offer 63. 股票的最大利润
喜欢 (0)