关于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;
};

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

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

关于leetcode:Leetcode-题解系列-股票的最大利润动态规划

题目相干

思路解析

暴力破解

动静布局

还能够更优吗