leetCode53. 最大子序和

109 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 currentSum = nums[0]; // 从第一个元素开始加
    for (let i = 0;i < nums.length; i++) {
      currentSum = (currentSum > 0) ? currentSum + nums[i] : nums[i];
      if (sum < currentSum) {
        sum = currentSum;
      }
    }
    return sum;
  }
guxuerui
版权声明:本站原创文章,由guxuerui于2020年04月14日发表,共计539字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)
Loading...