Question:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

  1. Input: [-2,1,-3,4,-1,2,1,-5,4],
  2. Output: 6
  3. Explanation: [4,-1,2,1] has the largest sum = 6.

Solution:

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var maxSubArray = function(nums) {
  6.     if(nums.length===0)return 0;
  7.     let max = nums[0];
  8.     for(let i=1; i<nums.length; i++){
  9.         if(nums[i]<nums[i]+nums[i-1]){
  10.             nums[i] = nums[i] + nums[i-1];
  11.         }
  12.         max = Math.max(max , nums[i]);
  13.     }
  14.     return max
  15. };

Runtime: 76 ms, faster than 48.44% of JavaScript online submissions for Maximum Subarray.

Memory Usage: 35.3 MB, less than 100.00% of JavaScript online submissions for Maximum Subarray.