Leetcode: Sword finger offer 42 Maximum sum of continuous subarrays

Enter an integer array , One or more consecutive integers in an array form a subarray . Find the maximum sum of all subarrays .

The required time complexity is O(n).

Example 1:

 Input : nums = [-2,1,-3,4,-1,2,1,-5,4]
 Output : 6
 explain :  Continuous subarray  [4,-1,2,1]  And the biggest , by  6.

Tips ：

• 1 <= arr.length <= 10^5
• -100 <= arr[i] <= 100
  Be careful ： This topic and the main station 53 The question is the same ：https://leetcode-cn.com/problems/maximum-subarray/

---

Their thinking

1. First define dp Array represents the largest subsequence ending with the current element and , Then traverse nums Array for each dp Element value , Finally, return the maximum value
2. State transition equation ：dp[i] = Math.max(nums[i], dp[i - 1] + nums[i])

Code

/** * @param {number[]} nums * @return {number} */
var maxSubArray = function(nums) {
    
    let dp = [nums[0]]
    for(let i = 1; i < nums.length; i ++) {
    
        dp[i] = Math.max(nums[i], dp[i - 1] + nums[i])
    }
    return Math.max(...dp)
};