JavaScript版《剑指offer》刷题（29）连续子数组的最大和

骑猪看日落 2021-10-24 04:56 129阅读 0赞

**题目描述**

输入一个整型数组，数组里面有正数，也有负数。数组中的一个或连续多个整数组成一个子数组。  
求所有子数组的和的最大值。要求时间复杂度为O(n)。

**题目分析**

思路一：暴力枚举，一个一个子数组计算

思路二：前面累加和加上当前值，其结果比当前值还小，说明前面的累加值还不如当前值开始，  
那么就重新计算子数组的起始位置，然后重复之前的步骤

思路三：动态规划

**代码**

思路一代码：

function subArray(array){
        let max = array[0],
            start = 0,
            end = 0;
        for(let i=0,len=array.length; i<len; i++) {
            let sum = 0;
            for(let j=i; j<len; j++) {
                sum += array[j];
                if(sum > max) {
                    max = sum;
                    start = i;
                    end = j;
                }
            }
        }
        //return max;
        return array.slice(start, end+1);
    }

思路二代码：

function findSubArray(arr) {
        if(arr.length < 1) {
            return 0;
        }
        let max = arr[0],
            sum = arr[0],
            start = 0,
            end = 0;
        for(let i=1, len=arr.length; i<len; ++i) {
            sum += arr[i];
            if(sum < arr[i]) {
                sum = arr[i];
            }
            if(sum > max) {
                max = sum;
            }
        }
        return max;
    }

思路三代码：

function subArray(array) {
        let arr = [],
            start = 0,
            end = 0;
        for(let i=0,len=array.length; i<len; i++) {
            if(i === 0 || arr[i-1] <= 0) {
                arr.push(array[i]);
            } else {
                arr.push(arr[i - 1] + array[i]);
            }
        }
        return arr.sort((a, b)=>a-b).pop();
    }
    
    
    console.log(findSubArray([6,-3,-2,7,-15,1,2,2]));

参考文章：  
https://www.cnblogs.com/echovic/p/6565521.html  
https://www.cnblogs.com/wuguanglin/p/FindGreatestSumOfSubArray.html  
https://github.com/DavidChen93/-offer-JS-/blob/master/42.1%20%E8%BF%9E%E7%BB%AD%E6%95%B0%E7%BB%84%E7%9A%84%E6%9C%80%E5%A4%A7%E5%92%8C.js

发表评论取消回复

表情：

评论列表（有 0 条评论，129人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指offer - 连续子数组的最大和

public class Solution { public int FindGreatestSumOfSubArray(int[] a) {

冷不防/ 2022年09月25日 01:28/ 0 赞/ 163 阅读

相关剑指offer：连续子数组的最大和

题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正

╰半橙微兮°/ 2022年08月05日 08:58/ 0 赞/ 171 阅读

相关剑指offer刷题（30）：连续子数组的最大和

剑指offer刷题（30）：连续子数组的最大和刷题平台：[牛客网][Link 1] 连续子数组的最大和考点：动态规划 1、题目描述 HZ偶尔会

雨点打透心脏的1/2处/ 2022年05月26日 23:05/ 0 赞/ 27 阅读

相关剑指Offer | 连续子数组的最大和

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

雨点打透心脏的1/2处/ 2022年05月23日 04:30/ 0 赞/ 182 阅读

相关剑指Offer:连续子数组的最大和

题目：输入一个整型数组,数组里有正也有负，数组中的一个或者多个连续整数，组成一个子数组，求所有子数组的和的最大值。输入1，-2,3,10，-4,7,2，-5。提一下，

女爷i/ 2022年04月25日 04:40/ 0 赞/ 212 阅读

相关剑指Offer-连续子数组的最大和

题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候

秒速五厘米/ 2022年04月24日 00:50/ 0 赞/ 210 阅读

相关剑指offer:连续子数组的最大和

题目描述例如:\{6,-3,-2,7,-15,1,2,2\},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和。 AC C

港控/mmm°/ 2022年04月10日 08:59/ 0 赞/ 207 阅读

相关【剑指Offer】（数组）连续子数组的最大和

题目链接：[https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=13&tqId=11

「爱情、让人受尽委屈。」/ 2022年03月16日 12:48/ 0 赞/ 207 阅读

相关 JavaScript版《剑指offer》刷题（29）连续子数组的最大和

题目描述输入一个整型数组，数组里面有正数，也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。题目分析思路

骑猪看日落/ 2021年10月24日 04:56/ 0 赞/ 130 阅读

相关剑指offer：连续子数组的最大和

试题： HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问

柔光的暖阳◎/ 2021年06月24日 16:09/ 0 赞/ 383 阅读