LeetCode Js-53. Maximum Subarray

    AllenLi
    LeetCode Js-Array

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

    給予一個 nums 的整數陣列，尋找連續的數列為最大的數列和，並回傳該數列。

    Example 1:

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

    Example 2:

    Input: nums = [1]
Output: 1

    Example 3:

    Input: nums = [5,4,-1,7,8]
Output: 23

    Solution:
    1. 先設定初始值為 nums[0]
    2. 有了起點後，運用++i依序往後比較
    3. 如果下一個 nums 大於 0，則將兩者相將
    4. 如果下一個 nums 小於 0，則將兩者取最大值
    5. 回傳結果

    Code:

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

    FlowChart:
    Example 1

    Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Array:          0 1  2 3  4 5 6  7 8
Length:         1 2  3 4  5 6 7  8 9
response = nums[0] //-2

step.1
i = 1
nums[i - 1] > 0 => (nums[0] = -2) < 0  //break                                     
response = Math.max(response, nums[i]) => Math.max(-2, -2) 
//response = -2

step.2
i = 2
nums[i - 1] > 0 => (num[1] = 1) > 0                                           -2
nums[i] = nums[2] + nums[2-1] => nums[2] = -3 + 1 = -2  //Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
response = Math.max(response, nums[i]) => Math.max(-2, -2)
//response = -2

step.3
i = 3
nums[i - 1] > 0 => (num[2] = -2) < 0  //break                                     
response = Math.max(response, nums[i]) => Math.max(-2, 4) 
//response = 4

step.4
i = 4
nums[i - 1] > 0 => (num[3] = 4) > 0                                                3
nums[i] = nums[4] + nums[4-1] => nums[4] = -1 + 4 = 3  //Input: nums = [-2,1,-2,4,-1,2,1,-5,4]
response = Math.max(response, nums[i]) => Math.max(4, -3)
//response = 4

step.5
i = 5
nums[i - 1] > 0 => (num[4] = 3) > 0                                                5
nums[i] = nums[5] + nums[5-1] => nums[5] = 2 + 3 = 5  //Input: nums = [-2,1,-2,4,3,2,1,-5,4]
response = Math.max(response, nums[i]) => Math.max(4, 5) 
//response = 5

step.6
i = 6
nums[i - 1] > 0 => (num[5] = 5) > 0                                                   6
nums[i] = nums[6] + nums[6-1] => nums[6] = 1 + 5 = 6  //Input: nums = [-2,1,-2,4,-1,5,1,-5,4]
response = Math.max(response, nums[i]) => Math.max(5, 6) 
//response = 6

step.7
i = 7
nums[i - 1] > 0 => (num[6] = 3) > 0                                                       1
nums[i] = nums[7] + nums[7-1] => nums[7] = -5 + 6 = 1  //Input: nums = [-2,1,-2,4,-1,2,6,-5,4]
response = Math.max(response, nums[i]) => Math.max(6, 1) 
//response = 6

step.8
i = 8
nums[i - 1] > 0 => (num[7] = 1) > 0                                                       5
nums[i] = nums[8] + nums[8-1] => nums[8] = 4 + 1 = 5  //Input: nums = [-2,1,-2,4,-1,2,6,1,4]
response = Math.max(response, nums[i]) => Math.max(6, 5) 
//response = 6

return response = 6

    Example 2

    Input: nums = [1]
response = nums[0] //1

step.1
i = 1
nums[i - 1] > 0 => (nums[0] = 1) > 0
response = Math.max(response, nums[i]) => Math.max(1, 1) 
//response = 1

return response //1

    Example 3

    Input: nums = [5,4,-1,7,8]
response = nums[0] //5

step.1
i = 1
nums[i - 1] > 0 => (nums[0] = 5) > 0                                     9
nums[i] = nums[1] + nums[1-1] => nums[1] = 4 + 5 = 9  //Input: nums = [5,4,-1,7,8]
response = Math.max(response, nums[i]) => Math.max(5, 9) 
//response = 9

step.2
i = 2
nums[i - 1] > 0 => (num[1] = 9) > 0                                          8
nums[i] = nums[2] + nums[2-1] => nums[2] = -1 + 9 = 8  //Input: nums = [5,4,-1,7,8]
response = Math.max(response, nums[i]) => Math.max(9, 8)
//response = 9

step.3
i = 3
nums[i - 1] > 0 => (num[2] = 8) > 0                                           15
nums[i] = nums[3] + nums[3-1] => nums[3] = 7 + 8 = 15  //Input: nums = [5,9,8, 7,8]
response = Math.max(response, nums[i]) => Math.max(9, 15)
//response = 15

step.4
i = 4
nums[i - 1] > 0 => (num[3] = 15) > 0
nums[i] = nums[4] + nums[4-1] => nums[4] = 8 + 15 = 23  //Input: nums = [5,9,-1,15,8]
response = Math.max(response, nums[i]) => Math.max(9, 23)
//response = 23

return response //23

    Remark:
    一開始嘗試暴力破解，使用雙「For迴圈」來將每一個連續數列，皆各別加總一輪。
    Two For Loops:

    var maxSubArray = function(nums) {
  let max: number = Math.min(...nums);

  for (let i = 0; i < nums.length; i++) {
    let sum = 0
    
    for (let j = i; j < nums.length; j++) {
      sum += nums[j]
      
      if (sum > max) {
        max = sum
      }
    }
  }
  return max
}

//雖然我們可以取出 nums 的最小值，來當作 nums[-1]的情況時，返回 -1 ，但因雙迴圈的方式會產生 Time Limit Exceeded。

    Related Posts