LeetCode Js-53. Maximum Subarray。

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

Solution:

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

Code:

var maxSubArray = function(nums) {
  let response = 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