首页 > 试题广场 >

子数组的最大累加和问题

[编程题]子数组的最大累加和问题
  • 热度指数:85501 时间限制: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

备注:

 public int maxsumofSubarray (int[] arr) {
        if(arr == null || arr.length == 0) return -1;
        
        int max = Integer.MIN_VALUE;
        int cur = 0;
        for(int i = 0; i < arr.length; i++){
            cur += arr[i];
            max = Math.max(cur, max);
            cur = cur < 0 ? 0 : cur;
        }
        return max;
    }
一个cur记录当前的累加和,如果累加和小于0,就没必要在这个基础上继续累加,归零继续往后面遍历
发表于 2020-08-18 20:00:31 回复(4)
这个题目的测试用例就有问题。憨的不行。
发表于 2020-09-12 21:54:39 回复(11)
从头到尾扫描一遍,累加,如果累加到0或者负数,说明前面的和对于后面的和没有正向贡献,因此累加重新开始,
没有减到0,说明对后面的还有正向贡献,因此继续累加。
注意要分别记录已经产生的最大累加值和当前累加值
    public int maxsumofSubarray (int[] arr) {
        int maxSum = 0;
        int sum = 0;
        for(int i = 0; i < arr.length; i++){
            sum = sum + arr[i] > 0 ? sum + arr[i] : 0;
            maxSum = maxSum > sum ? maxSum : sum;
        }
        return maxSum;
    }


编辑于 2021-07-27 19:26:22 回复(1)
//第一种:累加和小于0,则归零继续往后面遍历   
public int maxsumofSubarray (int[] arr) {
   
        if(arr==null||arr.length==0) return -1;
        int n=arr.length,max=0,sum=0;
        for(int i=0;i<n;i++){
            sum=sum+arr[i];
            if(sum>max)  max=sum;
            if(sum<0) sum=0;
            
        }
        return max;
    }
}
//第二种,dp 存储到第i个元素时的最大和
    public int maxsumofSubarray (int[] arr) {
       int n=arr.length,dp=0,max=0;
        for(int i=0;i<n;i++){
            dp=Math.max(arr[i],dp+arr[i]);
            max=Math.max(max,dp);
        }
        return max;
    }

发表于 2021-01-27 17:47:21 回复(0)
class Solution:
    def maxsumofSubarray(self , arr ):
        ans = 0
        cum = 0
        for i in arr:
            cum += i
            if cum < 0:
                cum = 0
            elif cum > ans:
                ans = cum
        return ans

发表于 2021-01-28 20:59:18 回复(1)
  public int maxsumofSubarray (int[] arr) {
        //1.dp状态设置: dp[i]就是以nums[i]为结尾的的连续子数组的最大和
        int[] dp = new int[arr.length];
        //2.初态设置:dp[0]必须包含nums[0] 所以:
        dp[0] = arr[0];
        int res = dp[0];
        //3.转移方程:
        //因为nums[i]无论如何都要包括 那么可以选择的余地就是dp[i-1]了
        //dp[i-1]<0 那么不如只选nums[i]了 dp[i-1]>0 那就nums[i]带上dp[i-1]
        for (int i = 1; i < arr.length; i++) {
           dp[i] =  dp[i-1]>0?dp[i-1]+arr[i]:arr[i];
           //由于无论如何都要包括nums[i] 那么如果最后的nums[len-1]<0
            //那么此时dp[len-1]肯定不是最大连续和 需要max筛选
            res = Math.max(res,dp[i]);
        }
        return res;
    }

发表于 2021-03-06 05:34:37 回复(2)

正确的代码不可以通过,错误代码可以通过.....呵呵

发表于 2020-09-16 15:52:18 回复(2)

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)
int maxsumofSubarray(vector<int>& arr) {
        // write code here
        int maxresult = 0;
        int curresult = 0;
        for(int i = 0;i<arr.size();i++)
        {
            curresult += arr[i];
            if(curresult < 0)
            {
                curresult = 0;
            }
            if(curresult > maxresult)
            {
                maxresult = curresult;
            }
        }
        return maxresult;
    }

发表于 2020-11-04 23:08:57 回复(0)
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)
class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here
        s :int = 0
        maxs : int = 0
        for i in arr:
            s += i
            if s<0:
                s = 0
            else:
                maxs = max(maxs,s)
        return maxs
发表于 2021-09-11 15:45:06 回复(0)
public class Solution {
    public int maxsumofSubarray (int[] arr) {
        int max = 0;
        int cumsum = 0;
        for(int i = 0; i < arr.length; i++){
            if(cumsum >= 0){
                cumsum += arr[i];
            }
            else{
                cumsum = arr[i];
            }
            max = Math.max(max, cumsum);
        }
        return max;
    }
}

发表于 2021-09-04 22:04:49 回复(0)
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)
#
# max sum of the subarray
# @param arr int整型一维数组 the array
# @return int整型
class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here
        num_c = 0
        num_r = arr[0]
        for i in range(len(arr)):
            num_c += arr[i]
            if i > 0:
                num_r = max(arr[i],num_c,num_r)
            if num_c < 0:
                num_c = 0
        return num_r

发表于 2021-08-06 21:44:53 回复(0)
        int maxsumofSubarray(vector<int>& arr) 
    {
        int temp = 0; int result = arr[0];
        for(int i=0;i<arr.size();i++)
        {
            temp = max(temp+arr[i],arr[i]);
            result = max(result,temp);
        }
        return result;
        // write code here
    }
遍历数组,看看是累加到当前元素的和大 还是当前元素大,并更新temp的值
发表于 2021-07-28 15:04:20 回复(0)
Python
遍历数组,只要累计和是负数就将累计和归零(累计和是负数证明对后面的累计和能否成为最大值是负面效应)
#
# max sum of the subarray
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here
        total = 0
        maxi = arr[0]
        for i in range(len(arr)):
            total = total + arr[i]
            if total <= 0:
                total = 0
            elif total >= maxi:
                maxi = total 
        return maxi
            
            


发表于 2021-04-17 18:19:57 回复(0)
有写go的小伙伴吗?
思路:
.子数组必然以正数开始,其实就是分析一个子结构,类似:[+a1, +a2, -a3, -a4, +a5]
.问题本质就是,在两个正子数组之间的负子数组是否应该被计算在内的问题
.如果负子数组元素和的绝对值分别小于前后正子数组的元素和,则应该被计算在内,否则前后正子数组的元素和的较大者为可能的结果。

package main

func maxsumofSubarray( arr []int ) int {
    res := 0
    tmp := 0
    for i := 0; i < len(arr); i++ {
        res += arr[i]
        if arr[i] > 0 && res <= 0 {
            res = arr[i]
        }
        if arr[i] < 0 && res > tmp{
            tmp = res
        }
    }
    return res
}

编辑于 2021-03-03 00:02:13 回复(1)
能贪心绝不动归
class Solution {
public:
    int maxsumofSubarray(vector<int>& arr) {
        int res=0;
        int sum=0;
        for(auto val : arr){  // 贪心
            if(sum<=0) sum=0;  // 和小于等于0直接抛弃
            sum += val;
            if(sum > res) res = sum;  // 更行最大值
        }
        return res;
    }
};


发表于 2021-02-26 10:45:11 回复(0)
class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxsumofSubarray(vector<int>& arr) {
        int a = arr.size();
        int dp[a];
        dp[0] = arr[0];
        for(int i = 1; i < arr.size(); i++){
            if(dp[i-1] >=0){
                dp[i] = dp[i-1]+arr[i];
            }
            else{
                dp[i] = arr[i];
            }
        }
        return dp[a-1];
    }
};
我不知道我这代码为什么能通过????这测试用例明显是错的
正确解法
class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxsumofSubarray(vector<int>& arr) {
        int a = arr.size();
        int dp[a];
        dp[0] = arr[0];
        int _max = dp[0];
        for(int i = 1; i < arr.size(); i++){
            if(dp[i-1] >=0){
                dp[i] = dp[i-1]+arr[i];
            }
            else{
                dp[i] = arr[i];
            }
            _max = max(_max, dp[i]);
        }
        return _max;
    }
};


发表于 2021-01-27 23:15:12 回复(4)
import java.util.*;


public class Solution {
    /**
     * 【逆向思维】要找出一个子串,使得和最大
     * 相对来说是去掉了左边和右边的数据,剩下一个子串
     * 所以用左右两个指针,依次找从左到右,从右到左的连续最小和index
     * 那么这两者之间的子串就是目标子串
     * 同时,需要考虑指针碰撞,也就是所有值为负数,那么找出其中的最大的单值
     */
    public int maxsumofSubarray (int[] arr) {
        if(arr.length <=1){
            return arr[0];
        }
        
        int leftMin = arr[0];
        int leftIndex = 0;
        int tmp = arr[0];
        // 保存最大值,用于指针碰撞后返回
        int max=arr[0];
        for(int i = 1; i < arr.length; i ++){
            tmp += arr[i];
            if(tmp < leftMin){
                leftMin = tmp;
                leftIndex = i;
            }
            
            if(arr[i]>max){
                max = arr[i];
            }
        }

        int rightMin = arr[arr.length-1];
        int rightIndex = arr.length-1;
        tmp = arr[arr.length-1];
        for(int j = arr.length-2; j >= 0; j --){
            tmp += arr[j];
            if(tmp < rightMin){
                rightMin = tmp;
                rightIndex = j;
            }
        }

        // 指针碰撞了,返回最大值
        if(leftIndex>=rightIndex){
            return max;
        }else{
            // 找到左右指针,同时要判断左右指针的值是否大于0
            tmp = 0;
            for(int k = leftIndex+1; k <= rightIndex-1; k ++){
                tmp += arr[k];
            }
            
            if(arr[leftIndex]>0){
                tmp += arr[leftIndex];
            }
            
            if(arr[rightIndex]>0){
                tmp += arr[rightIndex];
            }

            return tmp;
        }
    }
}


发表于 2020-12-27 20:47:10 回复(0)