Leetcode|Leetcode 题解系列 -- 股票的最大利润（动态规划） Leetcode题解系列--股票的最大利

本专题旨在分享刷Leecode过程发现的一些思路有趣或者有价值的题目。【当然是基于js进行解答】。
动态规划一样是leetcode 中等难度习题的重点类型之一，同时可能也是面试热点之一，所以重要性不言而喻。

文章图片

题目相关

原题地址: https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
题目描述：

示例1：
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。（注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。）
- 示例2：
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
- 限制：
<= 数组长度 <= 10^5

思路解析暴力破解首先有一部分同学喜欢上来就来一波暴力破解，直接计算出所有可能的组合情况:

文章图片

找出给定数组中两个数字之间的最大差值（即，最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）, 那么所有的组合情况就是n*(n-1)/2，复杂度是O(n^2),毫无疑问，在题目给定的0 <= 数组长度 <= 10^5下，妥妥超时；而且面试如果暴力破解的话，估计也要被暴力pass了。
动态规划（这个名字一听就很科学！）
其实早期详细写过动态规划的基础思路：https://segmentfault.com/a/11...
建议不熟悉的同学可以先去看看这一篇。
而所谓动态规划，核心就是就是把多阶段过程，转化为一系列单阶段问题；把问题不断拆解为子问题去求解。
如果看过基础篇的同学应该知道，这里说的拆解，其实更直白一些就是找到第i个子问题与前i个子问题的关系。
带入本道题其实就是把求解n天里买卖股票最高利润的问题，先转化为先求解第n天卖出股票时的最高利润，然后从中找出最大值即可。

文章图片

以输入 [7,1,5,3,6,4] 为例：

第1天卖出的话，最高利润是0，等于是无交易；
第2天卖出的话，最高利润是0，因为第二天价格是1，高出第1天，也不会交易；
第3天卖出的话，的最高利润是4，也就是第二天买入，第三天卖出；
以此类推...

来观察计算求解第i天卖出股票时，所能得到的最高利润的核心，只要已知目前为止的历史最低价，那么前i天的最高利润其实就是用第i天的价格减去这个历史最低价即可，那么思路不就来了？

文章图片

var maxProfit = function(prices) { const profit = []; // profit[i] 表示第i天卖出时的最大利润 let historyMinPrice = Infinity; for(let i = 0; i <= prices.length; i++) { // 保持更新迄今为止的历史最低价 if(prices[i] < historyMinPrice) { historyMinPrice = prices[i]; } profit[i] = prices[i] - historyMinPrice; } // 未完待续 // ... };

那么，有了这个price数组之后，只要获取其中的最大值，其实也就是题目所要求的输出了。这个想必难不倒大家，可以直接循环比对一次获得，但是其实思考下，并没必要再进行一次循环，因为在原来的循环过程，我们其实就可以沿用历史最低价的思路，另外维持一个目前为止的最大利润变量。也就是

var maxProfit = function(prices) { const profit = []; // profit[i] 表示第i天卖出时的最大利润 let historyMinPrice = Infinity; let maxProfit = 0; for(let i = 0; i <= prices.length; i++) { // 保持更新迄今为止的历史最低价 if(prices[i] < historyMinPrice) { historyMinPrice = prices[i]; } profit[i] = prices[i] - historyMinPrice; if(profit[i] > maxProfit) { maxProfit = profit[i]; } } return maxProfit; };

文章图片

还可以更优吗现在我们已经解出了这道题，那么就到此为止了吗？回头看看我们的代码，会发现是否有必要维持profit数组的存在呢？它的意义仅用于更新maxProfit而已那么是不是...
大胆一点！直接把它移除掉！！

var maxProfit = function(prices) { // 干掉profit[i] let historyMinPrice = Infinity; let maxProfit = 0; for(let i = 0; i <= prices.length; i++) { // 保持更新迄今为止的历史最低价 if(prices[i] < historyMinPrice) { historyMinPrice = prices[i]; }if(prices[i] - historyMinPrice > maxProfit) { maxProfit = prices[i] - historyMinPrice; } } return maxProfit; };

到这里是不是成就感更深了一层！