本题旨在分享在刷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<=arraylength<=10^5下，会正常超时；而如果面试被暴力破解，估计就暴力通过了。动态规划（这个名字听起来很科学！）其实我很早就把动态规划的基本思想写得很详细了：https://segmentfault.com/a/11...推荐不会的同学熟悉的可以先看这篇文章。所谓动态规划的核心是将多阶段过程转化为一系列单阶段问题；不断地将问题分解成子问题来解决。看过基础篇的同学应该知道，这里说的反汇编其实更直接的就是找到第i个子问题和前面第i个子问题的关系。带入这道题其实就是把求解n天买卖股票的最高利润问题转化为先求解第n天卖出股票时的最高利润，然后从中求最大值。以输入[7,1,5,3,6,4]为例：第一天卖出，最大利润为0，等于没有成交；如果第二天卖出，最大利润为0，因为第二天的价格为1，如果高于第一天，则不会成交；如果第三天卖出，最大利润为4，即第二天买入，第三天卖出；以此类推……观察并计算第i天卖出股票所能获得的最高利润的核心。只要知道目前为止的历史最低价，前i天的最高利润其实就是第i天的价格减去历史最低价就够了，思路是不是来了？varmaxProfit=function(prices){constprofit=[];//profit[i]表示第i天卖出的最大利润lethistoryMinPrice=Infinity;for(leti=0;i<=prices.length;i++){//继续更新到目前为止的历史最低价if(prices[i]
