LeetCode53. 最大子序和

106 views次阅读
没有评论

给定一个整数数组nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入:[-2, 1, -3, 4, -1, 2, 1, -5, 4] 输出:6 解释:连续子数组[4, -1, 2, 1]的和最大,为6

从题干中的最大、连续等词可得知,这道题属于动态规划,从数组第一项开始,每次将相加的两项之和保存下来,并与一个初始的最大和相比较,最后返回最大连续子数组的和。

  const maxSubArray = (nums) => {
    let sum = nums[0]; // 初始最大和,数组长度为一的时候直接返回
    let currentNum = nums[0]; // 循环变量,从数组第二项开始遍历
    for (let i = 1; i < nums.length; i++) {
      currentNum = (currentNum > 0 ? currentNum + nums[i] : nums[i]);
      if (sum < currentNum) {
        sum = currentNum;
      }
    }
    return sum;
  }
guxuerui
版权声明:本站原创文章,由guxuerui于2020年03月29日发表,共计593字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)
Loading...