浅聊一下

作为一名小白，在leetCode刷题数现已达到了三位数，可是在我刷过的大部分标题中，都是运用的暴力解法，多层循环遍历等等…真的是有受够了自己

LeetCode:生意股票的最佳时机

咱们先来看标题：

给定一个数组prices，它的第i个元素prices[i]表明一支给定股票第i天的价格。

你只能挑选某一天买入这只股票，并挑选在未来的某一个不同的日子卖出该股票。设计一个算法来核算你所能获取的最大赢利。

回来你能够从这笔买卖中获取的最大赢利。假如你不能获取任何赢利，回来0。

换做昨日的我估量在想，这这这，简单的不能再简单了，直接双层循环我就给他处理了…

可是今日，我挑选用动态规划和贪心来完结这道题

动态规划

咱们来看标题最终想要的成果是什么

=>回来你能够从这笔买卖中获取的最大赢利

注意 最大 这两个字，一般说到最大，咱们就要想到动态规划，咱们得用动态规划把这题干掉

那动态规划是怎样考虑的呢？

• 自顶而下

  咱们要让最终的成果为最优解，自然要让前面的每一步都是最优解，带入标题

  我能够挑选今日卖股票，也能够挑选昨日卖股票，在今日以前，咱们昨日卖掉股票所得的赢利是最大的，所以我该和今日比较，假如今日卖的比昨日更多，那么我就今日把股票卖了…

• 状况搬运方程

  根据咱们自顶向下的思想，咱们能够列出状况搬运方程

dp[i] = Math.max(dp[i-1],prices[i]-min)

dp[i]代表第i天卖出股票获利的最大值，假如第i天卖出的赢利比dp[i-1]大，那么咱们取得的最大赢利就为dp[i]，而且咱们知道，在第一天买入股票之后当天是不能卖出股票的，所以

dp[0] = 0

var maxProfit = function(prices) {
    const dp = new Array(prices.length).fill(0)
    let min = prices[0]
    for(let i = 1;i<prices.length;i  ){
        min = Math.min(prices[i],min)
        dp[i] = Math.max(dp[i-1],prices[i]-min)
    }
    return dp[prices.length-1]
};

咱们运用一个数组 dp 来保存每天卖出股票能够取得的最大赢利。数组 dp 的长度与股票价格数组 prices 的长度相同。数组 dp 中的每个元素 dp[i] 表明在第 i 天卖出股票能够取得的最大赢利。初始值都为0。

然后，咱们从数组的第二个元素开端遍历（i = 1），关于每个元素 prices[i]，咱们进行以下操作：

1. 核算在前 i-1 天中能够取得的最小买入价格 min。咱们运用 Math.min(prices[i],min) 来更新最小买入价格 min。prices[i] 表明当时的股票价格，假如这个价格比当时的最小买入价格 min 小，就更新最小买入价格为这个值。
2. 核算在第 i 天卖出股票能够取得的最大赢利。咱们运用 Math.max(dp[i-1], prices[i]-min) 来更新数组 dp 中的元素。dp[i-1] 表明在前 i-1 天中取得的最大赢利，由于咱们不能在同一天既买入又卖出股票。所以，在第 i 天卖出股票的最大赢利为 prices[i]-min，即当时股票价格减去前 i-1 天中的最小买入价格。然后，咱们运用 Math.max 函数来比较 dp[i-1] 和 prices[i]-min，取其中的较大值作为 dp[i] 的值。

经过遍历完好个数组，咱们得到了最大赢利。最终，咱们回来 dp[prices.length-1] 作为函数的成果。

贪心

咱们再来用贪心处理这道题

什么是贪心？就是我很贪心，总是想得到最多的东西…总是做出在当时看来是最好的挑选 不从全体最优上加以考虑 算法得到的是部分最优解。

• 在每一个价格上升的时间，咱们挑选将股票卖出以获取最大赢利；而在价格下降或持平的时分，咱们挑选保持最低买入价格。经过这样的战略，咱们能够在一次遍历中找到最大赢利，而不需求进行多次买卖。

var maxProfit = function(prices) {
   let min = prices[0]
   let profit = 0
   for(let i = 1;i<prices.length;i  ){
    if(prices[i] > prices[i-1]){
        profit = Math.max(prices[i]-min,profit)
    }else{
        min = Math.min(prices[i],min)
    }    
   } 
   return profit
};

首先，咱们初始化两个变量 min 和 profit，min 用于记载当时遍历到的最低买入价格，profit 用于记载当时的最大赢利，初始值都为0。

然后，咱们从数组的第二个元素开端遍历（i = 1），关于每个元素 prices[i]，咱们进行以下操作：

1. 假如当时价格 prices[i] 大于前一个价格 prices[i-1]，说明股票价格上升了。此刻咱们能够考虑将其卖出，并核算当时的赢利。咱们运用 Math.max(prices[i]-min, profit) 来更新当时的最大赢利。prices[i]-min 表明将当时股票卖出后的赢利，假如这个赢利比当时的最大赢利 profit 大，就更新最大赢利为这个值。
2. 假如当时价格 prices[i] 小于等于前一个价格 prices[i-1]，说明股票价格下降了或者持平了。此刻咱们需求考虑是否要更新最低买入价格 min。咱们运用 Math.min(prices[i], min) 来更新最低买入价格。prices[i] 表明当时的股票价格，假如这个价格比当时的最低买入价格 min 小，就更新最低买入价格为这个值。

经过遍历完好个数组，咱们得到了最大赢利。最终，咱们回来最大赢利作为函数的成果。

下班

想当聪明人的第一天完美结束…今日就写到这里吧！对了，最近大大在搞年度优异创作者投票活动，要是掘友们觉得小弟的文章让您有所收获，就给我投上一票吧！！！