53_max_subarray.js

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray01 = function(nums) {
    // O(N^2), O(1)
    let max = nums[0];
    for(let i=0;i<nums.length; i++) {
        let currentSum = 0;
        for(let j=i;j<nums.length; j++) {
            currentSum+=nums[j];
            max = Math.max(max, currentSum);
        }
    }
    return max;
};
// greedy
var maxSubArray02 = function(nums) {
    // O(N), O(1)
    let max = nums[0];
    let currentSum = 0;
    for(let j=0;j<nums.length; j++) {
      // if(currentSum+nums[j] < nums[j]){
      //   currentSum = nums[j]
      // }else{
      //   currentSum = currentSum+nums[j]
      // }
      // OR
      currentSum = Math.max(currentSum+nums[j], nums[j])
      max = Math.max(max, currentSum);
    }
    return max;
};

// DP means given a input, it will give out a output
// find the patterns at the sequence of the problem
// start from 1 item, then 2 items, then 3 items.
var maxSubArray03 = function(nums) {
    // O(N), O(N)

    // S(i) = 1. A[i] if i==0;
    //        2. max { S(i-1)+A[i], A[i] }
  
    let maxList = [nums[0]];
    for(let i=1; i<nums.length; i++) {
      maxList[i] = Math.max(maxList[i-1]+nums[i], nums[i])
    }
    return Math.max(...maxList);
};

// DP O(N), O(1)
var maxSubArray = function(nums) {
    // S(i) = 1. A[i] if i==0;
    //        2. max { S(i-1)+A[i], A[i] }
    let max = nums[0];
    for(let i=1; i<nums.length; i++) {
      if(nums[i-1] + nums[i] > nums[i]) nums[i] += nums[i-1];
      if(nums[i] > max) max = nums[i];
    }
    return max;
};