Topic describes

Given an array of integers, nums, find a contiguous subarray with the largest sum (the subarray contains at least one element) and return its largest sum. Example: input: [-- 2, 1, 3, 4, 1, 2, 1, 5, 4] output: 6: continuous subarray and maximum of [4, 1, 2, 1], is 6. Advanced: If you already have an O(n) solution, try a more sophisticated diet-and-conquer solution. Source: LeetCode link: https://leetcode-cn.com/problems/maximum-subarray Copyright belongs to the buckle network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.Copy the code

Their thinking

Idea 1: Dynamic programming time complexity O(n)

  • Subarrays contain at least one element; Initialize ans to nums[0];
  • Iterating through the elements of the array:
    • If sum > 0, sum has a gain effect on the result, and sum retains and adds the current traversal number
    • If sum <= 0, sum has no gain effect on the result and needs to be discarded, then sum is directly updated to the current traversal number
    • Compare the size of sum and ans, set the maximum value to ans, and return the result at the end of the walk

reference

code

/ * * *@param {number[]} nums
 * @return {number}* /
var maxSubArray = function(nums) {
 let ans=nums[0]
 let sum=0;
  for(let item of nums){
      if(sum>0){
          sum+=item
      }else{
          sum=item;
      }
    ans=Math.max(ans,sum);
  }
  return ans;

};
Copy the code