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;i0){
            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;
};