前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >最大子序和

最大子序和

作者头像
木子星兮
发布2020-07-16 17:22:27
3520
发布2020-07-16 17:22:27
举报
文章被收录于专栏:前端小码农

JavaScript实现LeetCode第53题:最大子序和

题目描述

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。示例:

代码语言:javascript
复制
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

解题思路

这是一道动态规划类的题目; 声明两个变量, currentSum: 之前连续几个值相加的和, maxSum: 当前最大的子序列和

  • 1.比较nums[i],跟currentSum加上nums[i]后的值, 将较大的赋值给currentSum;此时计算的是用上nums[i]的最大的子序列和,但不一定是整个过程中的最大子序和,需要第二步骤的判断;举例说明 :[1, 2, -1], 计算到第三个值是, currentSum为1+2-1=2, 但是在计算到第二个数的时候,它才是最大子序和,1 + 2 = 3, 所以需要声明一个变量maxSum, 来计算是否是当前最大的子序列和
  • 2.比较currentSum, maxSum, 将较大的值赋值给maxSum

代码实现

代码语言:javascript
复制
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let maxSum = nums[0];
    let currentSum = nums[0];
    for(let i = 1; i < nums.length; i++) {
        // 比较当前的和跟加上nums[i]后的值, 将较大的赋值给currentSum
        currentSum = Math.max(nums[i], currentSum+=nums[i]);
        // 比较currentSum, maxSum, 将较大的值赋值给maxSum
        maxSum = Math.max(currentSum, maxSum);
    }
    return maxSum;
};
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-03-05,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 牧码的星星 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 解题思路
  • 代码实现
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档