121_max_profit.js

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit01 = function(prices) {
  //   time: O(N^2)
 //    space: O(1)
  if(prices.length<=1) return 0;
   //   max = second - first; -6
  let max = prices[1] - prices[0];
   // start from first price of prices
  for (let i=0; i<prices.length; i++) {
    // then do delta value of each of the rest of list
    for(let j = i+1; j<prices.length; j++) {
      let delta = prices[j] - prices[i];
      // if the delta value is larger then current max, then override the max
      max = Math.max(delta, max);
    }
  }
  if(max < 0) return 0;
  
  return max;
};

// greedy solution
var maxProfit02 = function(prices) {
  //   time: O(N)
  //   space: O(1)
  // handle 
   //   empty, or only one item
  if(prices.length <= 1) return 0;
  let maxProfit = 0;
  let currentLowestBuyingPoint = Number.MAX_VALUE;
  for(let i=0; i<prices.length; i++) {
    if(prices[i] < currentLowestBuyingPoint) {
      currentLowestBuyingPoint = prices[i]
    }else{
      maxProfit=Math.max(prices[i]-currentLowestBuyingPoint, maxProfit)
    }
  }
  return maxProfit;
};

var maxProfit = function(prices) {
  // [] -> 0
  // [7] -> 0
  // [7,1] -> 0
  // [7,1,5] -> 4
  // [7,1,5,3] -> 4
  // [7,1,5,3,6] -> 5
  // [7,1,5,3,6,4] -> 5
  
  //   every time we see a new item
  //   we want to check if the diff(current-minPrice) is > maxSum;
  //   so we want to track maxSum and minPrice;
  const maxSumArr = [0];
  let minPrice = prices[0]
  let maxSum = 0;
  for(let i=1;i<prices.length;i++){
    if(prices[i]-minPrice > maxSum){
      maxSum = prices[i] - minPrice;
    }else if(prices[i]<minPrice){
      minPrice = prices[i];
    }
  }
  return maxSum;
}