首页 > 试题广场 >

子数组的最大累加和问题

[编程题]子数组的最大累加和问题
  • 热度指数：85502 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个长度为 n 的数组 arr ，返回其中任意连续子数组的最大累加和

题目保证没有全为负数的数据

数据范围：，数组中元素值
要求：时间复杂度为，空间复杂度为

示例1

输入

[1, -2, 3, 5, -2, 6, -1]

输出

12

说明

[3,6]范围内的子数组之和最大，3+5-2+6=12
示例2

输入

[1]

输出

1

备注:

算法知识视频讲解
添加回答
Javascript
暖暖1997头像 暖暖1997 
function maxsumofSubarray( arr ) {
    if(!arr){return 0;}
    let max = 0;
    let temp = 0;
    for(let i = 0 ; i<arr.length;i++){
        temp +=arr[i];
        if(temp<0){            
            temp = 0;
        }
        if(temp>max){
            max = temp;
        }
    }
    return max;
}
module.exports = {
    maxsumofSubarray : maxsumofSubarray
}; 

 //利用一个temp 看了一下题解，确实，如果说当前的累加值已经是负数，那就没必要记录，直接置0
 //从下一个位置重新开始

发表于 2021-09-21 11:57:14 回复(0)
Javascript
TarsWANG头像 TarsWANG 
function maxsumofSubarray( arr ) {
    // write code here
  let max = Number.MIN_VALUE
  let pre = 0
  for(let i = 0; i < arr.length; i++) {
    pre = Math.max(arr[i], pre + arr[i])
    max = Math.max(max, pre)
  }
  return max
}
module.exports = {
    maxsumofSubarray : maxsumofSubarray
};

发表于 2021-09-14 16:52:27 回复(0)
Javascript
王志晗头像 王志晗 
function maxsumofSubarray( arr ) {
    // write code here
    if(arr.length == 1) return arr[0];
    let sum = 0;
    let dp = arr[0];
    for(let i = 1; i < arr.length; i++){
        dp = dp + arr[i];
        if(dp < 0) dp = 0;
        if(dp > sum) sum = dp;
    }
    return sum;
}

发表于 2021-08-28 20:03:15 回复(0)
Javascript
牛客409004206号头像 牛客409004206号
function maxsumofSubarray( arr ) {
    // write code here
    if(arr.length==1) return arr[0]
    
    var dp1=arr[0]
    var dp2=arr[0]
    for(let i=1;i<arr.length;i++){
        if(arr[i]>0){
             dp2=Math.max(dp2+arr[i],arr[i],dp2)
           
        }else{
             if(dp2+arr[i]<0){
                 dp2=0
             }else{
             dp2=Math.max(dp2+arr[i],0,dp2)
                 
             }
            
        }
       dp1=Math.max(dp1,dp2)

        
    }
    return dp1
}
module.exports = {
    maxsumofSubarray : maxsumofSubarray
};
发表于 2021-08-24 00:17:43 回复(1)
JavaScript
白下布衣头像 白下布衣
胡扯吧，我拷贝所谓“通过代码”， 运行根本不通过，我看到通过代码本身的确写的不对，什么叫“子数组”？连续元素才叫子数组，如果可以断断续续，那叫子集，而不是子数组。过不了是应该的，但是之前又是怎么提交上去的呢？牛客网的细节不行
发表于 2021-04-08 01:32:34 回复(0)
JavaScript
啦啦啦20190328110888头像 啦啦啦20190328110888
思路：动态规划
状态公式：dp[i] = max(dp[i-1]+val,val)；
优化：不需要构建dp数组，只需要保存上一个状态，即可得到当前状态 
function maxsumofSubarray( arr ) {
    let max;
    let pre = arr[0];//用于保存上一个状态
    max = pre;//保存最大值
    for(let i =1;i<arr.length;i++){
        let nows;
        nows=Math.max(pre+arr[i],arr[i]);
        if(nows>max){
            max = nows;
        }
        pre = nows;
    }
    return max;
    
}


编辑于 2021-04-05 21:15:56 回复(0)
JavaScript
splwany头像 splwany

js榜都是错的，怎么通过的都？

思路：

  1. 设置一个变量max存储全局最大值，一个变量cur存储当前的和；

  2. 然后开始遍历数组:

    1. 将cur加上当前的值获得新cur；
    2. 如果新cur小于0，则重置cur为0，并继续下一循环；
    3. 如果新cur大于max，则更新max； 
function maxsumofSubarray( arr ) {
    let max = 0, cur = 0;
    for (const num of arr) {
        cur += num;
        if (cur < 0) cur = 0;
        else if (max < cur) max = cur;
    }
    return max;
}
编辑于 2021-04-03 15:35:13 回复(0)
JavaScript
张五哥头像 张五哥 
/**
 * max sum of the subarray
 * @param arr int整型一维数组 the array
 * @return int整型
 */
function maxsumofSubarray( arr ) {
    // write code here
    let maxRight = 0,
        maxLeft = 0,
        rightEndIndex = -1;
    for(let i =0 ; i< arr.length; i++) {
        maxRight += arr[i];
        maxLeft += arr[arr.length - i - 1];
        
        if(maxRight < 0) {
            maxRight = 0;
        }
        if(maxLeft < 0) {
            maxLeft = 0;
            rightEndIndex = arr.length - i - 1;
        }
    }

    if(rightEndIndex !== -1) {
        for(let i =arr.length - 1; i>=rightEndIndex; i--) {
            maxRight -= arr[i];
        }
    }
    
    return maxRight;
}
module.exports = {
    maxsumofSubarray : maxsumofSubarray
};


发表于 2021-03-01 10:44:19 回复(0)
JavaScript
牛客932857322号头像 牛客932857322号
function maxsumofSubarray( arr ) { 
   let currentMax = arr[0]
   for(let i = 1; i<arr.length; i++) {
       if(arr[i] + currentMax > currentMax) {
           currentMax = arr[i] + currentMax 
       }
    }
    return currentMax
}

//还有比这个简单的吗各位
发表于 2021-02-21 10:44:13 回复(0)
JavaScript
牛客435062230号头像 牛客435062230号
function maxsumofSubarray( arr ) {
    // write code here
    let sum = 0, res = 0;
    for(let i=0; i<arr.length; i++){
        sum+=arr[i];
        sum = Math.max(sum,0);
        res = Math.max(res,sum);
    }
    for(let i=0; i<arr.length; i++){
当最大累加和等于数组最大值则证明没有进行累加
        if(arr[i] == res){
          res += Math.max(arr[i+1],arr[i-1]); 
        }
    }
    return res;
}、、
发表于 2020-12-26 12:52:14 回复(0)
JavaScript
别卷啦！头像 别卷啦！
初始情况：
dp[0] = arr[0]
arr[i] > 0，那么 dp[i] = arr[i] + dp[i - 1]
arr[i] <= 0，那么 dp[i] = arr[i]
优化成连续原地动态规划，空间复杂度降为O(1)
 
function maxsumofSubarray( arr ) {
    // write code here
    let max = arr[0], l = arr.length
    for(let i = 1; i < l; i++){
        if(arr[i-1] > 0) arr[i] += arr[i - 1]
        max = Math.max(max, arr[i])
    }
    return max
}

编辑于 2021-06-18 10:50:18 回复(0)
JavaScript
牛客378745591号头像 牛客378745591号
function getMax(arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }

    let max = 0;
    let cur = 0;
    for (let i = 0; i < arr.length; i++) {
        cur += arr[i];
        max = Math.max(max, cur); // 每轮都去最大的值
        // 抛弃为负数的值，1 和 -2 相加 则为 -1，结果为负数，抛弃它，重新设置为0，从3这里从新开始累加
        cur = cur < 0 ? 0 : cur;
    }
    return max;
}
发表于 2020-09-11 11:45:26 回复(0)
提交观点

问题信息

动态规划 分治
难度：
12条回答 9408浏览

热门推荐

通过挑战的用户

相关试题

子数组的最大累加和问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号