The topic of dry

Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.

Example 1:

Input: nums = [-- 2, 1, 3, 4, 1, 2, 1, 5, 4] output: 6: continuous subarray and maximum of [4, 1, 2, 1], is 6.Copy the code

Greed

This problem is mainly to find a subproblem, the subproblem each cycle to record the sum of the preceding value, but if to the current element, the sum of the preceding value is less than 0, it is discarded, because the sum of our subsequence is meaningless after 0. Because if the sum of our sequences is negative, there’s no point in adding them.

Check out this animation: Practice Addresses

Code:

Execution time: 96 ms, beating 87.54% of users in all JavaScript commits

Memory consumption: 38.6 MB beats 99.67% of all JavaScript commits

 var maxSubArray = function (nums) {
    let per = nums[0]
    let maxCount = nums[0]
    for (let i = 1; i < nums.length; i++) {
        per = per < 0 ? nums[i] : per + nums[i]
        maxCount = Math.max(maxCount, per)
    }
    return maxCount
};
Copy the code