题目
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。
注意:你不能在买入股票前卖出股票。
示例
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
解答
- 不能在买入前卖出股票,也就说明我们没法直接找数组中的最大值和最小值求得最大利润
- 如果找到最小值,然后求得最小值右边的最大利润,会遗漏其他的最大利润情况,如右图。
采用动态规划,求得每个点的最大利润,然后进行比较求得最后的最大利润值
- 查找当前值左半区域的最低点,求得最大利润
-
答案
var maxProfit = function(prices) { if(prices.length === 0) return 0 let minPrice = prices[0], // 最小值 maxProfit = 0; // 最大利润 for(let i=0;i<prices.length;i++) { if(prices[i] < minPrice) { //如果当前值 小于 最小值 ,说明股票下跌 minPrice = prices[i] // 最小值就为当前值 }else if(prices[i]-minPrice > maxProfit) { // 如果当前最大利润 大于 最大利润,最大利润就等于当前最大利润 maxProfit = prices[i] - minPrice } } return maxProfit };
优化
var maxProfit = function(prices) { if(prices.length === 0) return 0 let minPrice = prices[0], // 最小值 maxProfit = 0; // 最大利润 for(let i=1;i<prices.length;i++) { if(prices[i] < minPrice) { //如果当前值 小于 最小值 ,说明股票下跌 minPrice = prices[i] // 最小值就为当前值 } // 比较 当前最大利润 和 最大利润 ,取最大值 maxProfit = Math.max(prices[i]- minPrice ,maxProfit) } return maxProfit };