首页 > 试题广场 >

子数组的最大累加和问题

[编程题]子数组的最大累加和问题

热度指数：85502 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 n 的数组 arr ，返回其中任意连续子数组的最大累加和

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

数据范围： $1 \le n \le 100000$ ，数组中元素值 $|val| \le 100$

要求：时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$

示例1

输入

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

输出

说明

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

示例2

输入

[1]

输出

备注:

算法知识视频讲解

Java

是小王吖🐅

import java.util.*;


public class Solution {
    /**
     * max sum of the subarray
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxsumofSubarray (int[] arr) {
        // write code here
        int max=0;
        int sum=0;
        for(int pos=0;pos<arr.length;pos++){
            sum+=arr[pos];
            max=Math.max(max,sum);
            if(sum<0){
                sum=0;
                continue;
            }
        }
        return max;
    }
}

发表于 2022-02-21 17:53:54 回复(0)

Java

KrystalZ

public class Solution {
    /**
     * max sum of the subarray
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxsumofSubarray (int[] arr) {
        // write code here
        int m = arr.length;
        int[] dp = new int[m];
        Arrays.fill(dp, Integer.MIN_VALUE);
        int maxSum = Integer.MIN_VALUE;
        for(int i=0;i<m;i++){
            dp[i] = getDp(arr, i, dp);
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
        
    }
    
    public int getDp(int[] arr, int n, int[] dp){
        if(n == 0) return arr[0];
        if(dp[n]!=Integer.MIN_VALUE) return dp[n];
        return Math.max(arr[n], dp[n-1]+arr[n]);
    }
}

发表于 2021-09-23 11:09:23 回复(0)

Java

菲尼克斯弗兰克

public class Solution {
    // 状态压缩的dp问题
    public int maxsumofSubarray (int[] arr) {
        int max = arr[0], pre = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (pre + arr[i] > arr[i]) pre = pre + arr[i];
            else pre = arr[i];
            max = Math.max(pre, max);
        }
        return max;
    }
}

发表于 2021-09-23 10:33:40 回复(0)

Java

何京洲

import java.util.*;


public class Solution {
    /**
     * max sum of the subarray
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxsumofSubarray (int[] arr) {
        // write code here
        int res=0;
        int sum=0;
        for(int i=0;i<arr.length;i++){
            sum=sum+arr[i];
            if(sum>res){
                res=sum;
            }
            if(arr[i]<0&&sum<0){
                sum=0;
                continue;
            }
        }
        return res;
    }
}

发表于 2021-09-10 15:45:03 回复(0)

Java

牛气嘣嘣

从数组索引1处，开始遍历
如果之前的累加和大于零，则arr[i] += arr[i - 1];
用Math.max更新返回结果的值。

发表于 2021-09-08 09:28:15 回复(0)

Java

向小牛牛学习吃嘛嘛香

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)

Java

key_J

      public int maxsumofSubarray (int[] arr) {
        // write code here
        int length = arr.length;
        int tmp = 0;
        int sum = Integer.MIN_VALUE;
        for (int i = 0; i < length; i++) {
            tmp += arr[i];
            if (arr[i]>tmp) tmp = arr[i];
            sum = Math.max(tmp,sum);
        }
        return sum;
    }

发表于 2021-09-02 15:35:35 回复(0)

Java

jsysisnz

public int maxsumofSubarray (int[] arr) {
        // write code here
        int sum=0,max=0;
        for(int i=0;i<arr.length;i++){
            if(arr[i]>0){
                sum+=arr[i];
            }
            else{
                sum=Math.max(sum+arr[i],0);
            }
            max=Math.max(max,sum);
        }
        return max;
    }

发表于 2021-08-30 11:23:29 回复(0)

Java

男神20190129221786

import java.util.*;

public class Solution {
    /**
     * max sum of the subarray
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxsumofSubarray (int[] arr) {
        // write code here
        int cur = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < arr.length; i++){
            cur += arr[i];
            max = Math.max(cur,max);
            cur = cur < 0 ? 0 : cur;
        }
        return max;
    }
}

发表于 2021-08-26 19:44:42 回复(0)

Java

谁是谁的眼

public int maxsumofSubarray (int[] arr) {
// write code here
int[] dp = new int[arr.length];
dp[0] = arr[0];
int res = dp[0];

for(int i = 1; i < arr.length; i++){
dp[i] = Math.max(arr[i],dp[i-1]+arr[i]);
res = Math.max(dp[i],res);
}

return res;
}

发表于 2021-08-22 20:56:18 回复(0)

Java

黄牛牛

import java.util.*;


public class Solution {
    /**
     * max sum of the subarray
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxsumofSubarray (int[] arr) {
        // write code here
        if (arr.length == 0) return 0;
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        int resMax = dp[0];
        for (int i=1; i < arr.length;i++) {
            if (dp[i-1] > 0) dp[i] = arr[i] + dp[i-1];
            else dp[i] = arr[i];
            resMax = Math.max(resMax, dp[i]);
        }
        return resMax;
    }
}

发表于 2021-08-20 15:36:39 回复(0)

Java

沉默着忍受

import java.util.*;


public class Solution {
    /**
     * max sum of the subarray
     * @param arr int整型一维数组 the array
     * @return int整型
     */
     public int maxsumofSubarray (int[] arr) {
        // write code here

        if(arr==null||arr.length==0) return 0;
        int max = arr[0];
        
        int count = 0;
        for(int i = 0;i<arr.length;i++){
            count+=arr[i];
            max = Math.max(count,max);
            max = Math.max(max,arr[i]);
            if(max<=0){
             count=0;
            }
        }
        return max;
    }
}

发表于 2021-08-17 17:05:56 回复(0)

Java

ㅤ201910241513431

//有点蠢的办法哈哈
public int maxsumofSubarray (int[] arr) {
        // write code here
        if(arr.length<=0) return 0;
        int left=0,right=arr.length-1;
        int max=Arrays.stream(arr).sum();
        ArrayList<Integer> list =new ArrayList<>();
        list.add(max);
        while(left<=right){
            if(arr[left]<=arr[right]){
                max=max-arr[left];
                list.add(max);
                left++;
            }else{
                max=max-arr[right];
                list.add(max);
                right--;
            }
    }
        return Collections.max(list);
        
    }
}

发表于 2021-08-06 12:39:18 回复(0)

Java

TylerChen

import java.util.*;


public class Solution {
    /**
     * max sum of the subarray
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    
    public int maxsumofSubarray (int[] arr) {
        int max = arr[0], curMax = arr[0];
        for(int i = 1; i < arr.length; i ++){
            curMax = Math.max(arr[i], arr[i] + curMax);
            max = Math.max(max, curMax);
        }
        return max;
    }
    public int maxsumofSubarray2 (int[] arr) {
        //dp[i] 为以arr[i]为结尾的子数组的最大累加和
        //dp[i] = max(arr[i] + dp[i-1], arr[i])
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        int max = dp[0];
        
        
        for(int i = 1; i < arr.length; i ++){
            dp[i] = Math.max(arr[i], arr[i] + dp[i-1]);
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

发表于 2021-07-31 14:28:09 回复(0)

Java

牛客397508259号

从头到尾扫描一遍，累加，如果累加到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)

Java

一个小小小小萌新

/**  * 对于此类问题，首先要理清思路，最大子段和怎么求，  * 第一步，需要用一个循环，遍历以每个数组元素开头的子段，  * 其次，需要记录以i元素开头的子段和以作比较  * 接着，因为已保证没有全是负数的数组，所以可以想到要除去累加和为负的子段，从新开始  * 最后比较得到最大子段和sum  */
                 int sum = arr[0], temp = arr[0];
            for (int j = 1; j < arr.length; j++) {
                if (temp > 0) {
                    temp += arr[j];
                } else {
                    temp = arr[j];
                }
                if (sum < temp) {
                    sum = temp;
                }
            }

编辑于 2021-07-24 20:08:25 回复(0)

Java

牛客507555376号

import java.util.*;


public class Solution {
    /**
     * max sum of the subarray
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxsumofSubarray (int[] arr) {
        if(arr == null || arr.length == 0){
            return 0;
        }
        int res = Integer.MIN_VALUE;
        int sum = 0;
        for(int i=0;i<arr.length;++i){
            sum += arr[i];
            if(sum <= 0){
                sum = 0;
            }else{
                res = Math.max(res,sum);
            }
        }
        return res;
    }
}

发表于 2021-05-17 09:29:47 回复(0)

Java

wjp-niuke

java动态规划

import java.util.*;

public class Solution {
/**
* max sum of the subarray
* @param arr int整型一维数组 the array
* @return int整型
*/
//动态规划
public int maxsumofSubarray (int[] arr) {
// write code here
if (arr.length==0) {
return 0;
}
if (arr.length==1) {
return arr[0];
}
int[] dp = new int[arr.length];
dp[0] = arr[0];
int result = arr[0];
for (int i = 1; i < arr.length; i++) {
dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
result = Math.max(result, dp[i]);
}
return result;
}
}

发表于 2021-04-05 11:10:29 回复(0)

Java

惠灵顿靖

public class Solution {
         public int maxsumofSubarray (int[] arr) {
             int cur=0,max=0;
             for(int i=0;i<arr.length;i++)
             {
                 cur=cur+arr[i];
                 cur=cur>0?cur:0;
                 max=max>cur?max:cur;
             }
             return max;
    }
}

发表于 2021-03-31 23:27:24 回复(0)