4、动态或贪心

1、买卖股票的最佳时机—*

根据股价手势数组，计算出最大收益，只能交易一次。如[7,1,5,3,6,4]，第2天买入，第5天卖出，最大收益5

var maxProfit = function (prices) {
    var arr = [];
    for (let i = 1; i < prices.length; i++) {
        arr.push(prices[i] - prices[i - 1]);
    }
    // 后一个更大，还是相加更大；把最大值放在数组中
    var max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        arr[i] = Math.max(arr[i], arr[i] + arr[i - 1])
        max = Math.max(max, arr[i]);
    }
    return max > 0 ? max: 0;
};

let maxProfit = function(prices) { // 最大值减最小值
    let max = 0;
    let min = Number.MAX_VALUE;
    
    for (let i = 0; i < prices.length; i++) {
        if (prices[i] < min) {
            min = prices[i];    
        } else if (prices[i] - min > max) {
            max = prices[i] - min;    
        }
    }
    return max;
};

2、买卖股票的最佳时机—*

根据股价手势数组，计算出最大收益，可以多次交易，但只能一支股票。如[7,1,5,3,6,4]，第2天买入，第3天卖出，第4天买入，第5天卖出，最大收益7

var maxProfit = function (prices) {
  let sum = 0;
  let min = Number.MAX_VALUE;
  let max = 0;
  for(let i = 0; i < prices.length; i++) {
    if (prices[i] < min) {
      min = prices[i];
    } else if (prices[i] - min > max) {
      max = prices[i] - min;    
    }
    if (prices[i] > prices[i + 1]) {
      sum += max;
      min = Number.MAX_VALUE;
      max = 0;
    }
  }
  return sum + max;
};

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

4、最大子序列和—*

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

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

var maxSubArray = function(nums) {
  const nLen = nums.length;
  let max = nums[0];
  let lastMax = 0;

  for (let i = 0; i < nLen; i++) {
    lastMax += nums[i];
    if (lastMax > max) {
      max = lastMax;
    }
    if (lastMax < 0) {
      lastMax = 0;
    }
  }
  return max;
};