题目

思路

啊啊啊啊啊又做不出来简单题了。不过贪心的思路有想到，一点安慰。
感觉贪心比动态规划好理解

动态规划

分为 dp[i][0]，和dp[i][1]这样的二维数组
dp[i][0] 表示第i天持有股票所得最多现金，可以是负数
dp[i][1] 表示第i天不持有股票所得最多现金
如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

• 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
• 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]

那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);
如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来

• 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
• 第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1][0]

同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

const maxProfit = prices => {
  const len = prices.length;
  // 创建dp数组
  const dp = new Array(len).fill([0, 0]);
  // dp数组初始化
  dp[0] = [-prices[0], 0];
  for (let i = 1; i < len; i++) {
    // 更新dp[i]
    dp[i] = [
      Math.max(dp[i - 1][0], -prices[i]),
      Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0]),
    ];
  }
  return dp[len - 1][1];
};

贪心

var maxProfit = function(prices) {
  //维护最小值，更新最大利润
  let min =prices[0]
  let profit =0
  for(let i=1;i<prices.length;i++){
    min =Math.min(min,prices[i])
    profit =Math.max(profit,prices[i]-min)
  }


  return profit
};

暴力法

超时啦
哈哈哈

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

    return max
};