最大子序和

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

题目描述

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

输入: [-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

代码实现

/**
 * @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;
};

本文分享自微信公众号 - 牧码的星星(gh_0d71d9e8b1c3),作者:木子星兮i

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 移除链表元素

    此时可以通过哨兵节点去解决它,哨兵节点广泛应用于树和链表的中,如伪头,伪尾,标记等,他们是纯功能的,通常不保存任何数据,其目的就是使得链表标准化,如使链表永不为...

    木子星兮
  • 三数之和

    给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三...

    木子星兮
  • 要实现60FPS动画, 你需要了解这些

    60FPS, 即每秒渲染60帧, 每一帧的间隔时间为 1000ms / 60 = 16.666ms

    木子星兮
  • 真实经历:手机浏览器被劫持了怎么办?

    明月作为一名草根博客站长手机端拥有几个测试网站移动端效果的浏览器是很正常的吧,可就是在前两天入手了红米 5 Plus 后(可参考【新入手 红米 5 Plus 手...

    明月云服务
  • SpringMVC系列之SpringMVC快速入门 MVC设计模式介绍+什么是SpringMVC+ SpringMVC的作用及其基本使用+组件解析+注解解析

    SpringMvc是一种基于java的实现Mvc设计模式的请求驱动类型的轻量级web框架,属于SpringFrameWork的后续产品,已经融合在Spring ...

    一只胡说八道的猴子
  • UIPageViewController电子书翻页效果

    且行且珍惜_iOS
  • 三分钟带你看遍世界大学排行

    代码大学,一直都是神圣的学习知识的殿堂,各个世界级名校都不断地为社会输送着人才,今天我们就来盘一盘世界大学的排名情况。

    周萝卜
  • SpringMVC系列 MVC设计模式介绍+ SpringMVC的作用及其基本使用+组件解析+注解解析

    SpringMvc是一种基于java的实现Mvc设计模式的请求驱动类型的轻量级web框架,属于SpringFrameWork的后续产品,已经融合在Spring ...

    一只胡说八道的猴子
  • LeetCode 334. 递增的三元子序列

    如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1, 使得 arr[i] < arr[j] < arr[k] ,返回 true...

    Michael阿明
  • PCIe系列第八讲、MSI和MSI-X中断机制

    本章将着重讲述PCIe的MSI和MSI-X中断机制,在FPGA应用中主要通过XDMA中断与上位机进行通信,本文略长。

    根究FPGA

扫码关注云+社区

领取腾讯云代金券