题目相干

原题地址: 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;};

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

那么本题的解答也就到此结束了，下期再见！