首页 > 试题广场 >

子数组的最大累加和问题

[编程题]子数组的最大累加和问题
  • 热度指数:2857 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个数组arr,返回子数组的最大累加和
例如,arr = [1, -2, 3, 5, -2, 6, -1],所有子数组中,[3, 5, -2, 6]可以累加出最大的和12,所以返回12.
[要求]
时间复杂度为,空间复杂度为


输入描述:
第一行一个整数N。表示数组长度
接下来一行N个整数表示数组内的元素


输出描述:
输出一个整数表示答案
示例1

输入

7
1 -2 3 5 -2 6 -1 

输出

12 

备注:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define max(a,b) ((a) > (b) ? (a) : (b))

int main(void) {
    int n, *arr;
    scanf("%d", &n);
    arr = (int *) malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
    
    int maxSum = INT_MIN, pre = -1, cur;
    for (int i = 0; i < n; i++) {
        cur = arr[i] + (pre > 0 ? pre : 0);
        maxSum = max(maxSum, cur);
        pre = cur;
    }
    printf("%d\n", maxSum);
    return 0;
}

发表于 2022-04-04 21:10:09 回复(0)
n=int(input())
number_list=list(map(int,input().split()))
dp=[number_list[i] for i in range(len(number_list))]
for i in range(1,len(number_list)):
    dp[i]=max(dp[i],dp[i-1]+number_list[i])
print(max(dp))

令dp[i]表示第i个位置时的最大值,则有递推方程dp[i]=max(dp[i],dp[i-1]+number_list[i])(前一个最大值加上当前数字是否是最大的,比如如果number_list[i]是负数就可能不是最大,不断的取最大的进行更新)
编辑于 2021-06-11 08:39:29 回复(0)
动态规划,用dp表示之前数组元素的最大累加和,如果是非负的,说明前面的元素做的是正向贡献,否则dp重新从arr[i]开始加。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] strArr = br.readLine().trim().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(strArr[i]);
        int dp = 0, res = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++){
            if(dp >= 0){
                dp += arr[i];
                res = Math.max(res, dp);
            }else
                dp = arr[i];
        }
        System.out.println(res);
    }
}

发表于 2021-05-27 22:22:29 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, x, Max=0;
    cin>>n;
    for(int i=0,s=0;i<n;i++){
        cin>>x;
        s += x;
        if(s<0)
            s = 0;
        else
            Max = max(Max, s);
    }
    cout<<Max<<endl;
    return 0;
}

发表于 2020-01-25 03:28:02 回复(0)
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += arr[i];
            max = Math.max(sum, max);
            if (sum < 0) {
                sum = 0;
            }
        }

        System.out.println(max);
    }
}
发表于 2019-10-11 18:36:18 回复(0)
const N = Number(readline());
const arr = readline().split(' ').map(Number);

const dp = [];
// 考虑的角度是寻找以 i 结尾的子数组中,累加和最大的。
// 先用 maxIdx 记下对于每个 i 位置而言, arr[0...i] 的累加和,其中最大的
// 累加和出现的位置。因为对于每个 i 位置而言,从下标 0 开始到 i,已经是以 i
// 结尾的最大子数组长度了,此时 maxIdx 位置,也必将是最终累加和最大的子数组
// 的结尾的位置。因为当你从下标 1, 2, 3, ... i - 1 开始时,子数组长度是在
// 不断缩短的,假如 1 ~ i-1 位置上都是正数,那显然缩短的过程中,以 maxIdx结尾
// 的子数组的累加和会不断减小。假如 1 ~ i-1 上有负数,则在缩短过程中,以 maxIdx
// 结尾的子数组的累加和还有可能增大。
// 为什么最大累加和的子数组一定以 maxIdx 位置结尾?
// 因为在从下标0开始的统计中,maxIdx之后位置结尾的累加和都已经开始变小了,说明
// maxIdx+1 ~ i (i > maxIdx+1)范围上存在负数,以之结尾的子数组累加和是不可能
// 超过maxIdx结尾的子数组累加和的。
let maxIdx = 0;
// 给原始arr前面插入一个0,方便统一从原始arr的第一个元素开始计算累加和。
arr.unshift(0);
for (let i = 1; i < N + 1; i++) {
  arr[i] = arr[i - 1] + arr[i];
  if (arr[i] > arr[maxIdx]) {
    maxIdx = i;
  }
}
// 最终的最大累加和子数组一定以maxIdx结尾,下来只需把i从原始arr的第一个下标开始一直缩短到
// maxIdx - 1位置,寻找这个过程中还有没有可能使累加和变大,
// 因为给arr前面插入了一个0,所以下标从1开始,
let max = arr[maxIdx];
for (let i = 1; i < maxIdx; i++) {
  arr[maxIdx] = arr[maxIdx] - arr[i];
  max = Math.max(max, arr[maxIdx]);
}
console.log(max);


发表于 2021-04-02 22:01:31 回复(0)
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        while(in.hasNext()){
            int N=in.nextInt();
            String[] arr=new String[N];
            int[] brr=new int[N];
            for (int i = 0; i <N ; i++) {
                arr[i]=in.next();
                brr[i]=Integer.valueOf(arr[i]);
            }
            int sum = sum(brr);
            System.out.println(sum);
        }
    }
    public static int sum(int[] arr){
        int max=0;
        int[] dp=new int[arr.length];
        for (int i = 0; i <arr.length ; i++) {
            if (i==0){
                dp[i]=arr[i]>0?arr[i]:0;
            }else {
                dp[i] = (dp[i - 1] + arr[i]) > 0 ? dp[i - 1] + arr[i] : 0;
            }
            max =  Math.max(max,dp[i]);
        }
        return max;
    }
}

编辑于 2020-10-04 03:48:01 回复(0)
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int arrayLength = scanner.nextInt();
        int[] inputarray = new int[arrayLength];
        for(int i = 0; i < arrayLength; i++){
            inputarray[i] = scanner.nextInt();
        }
        Main result = new Main();
        int finalresult = result.maxsubarray(inputarray);
        System.out.println(finalresult);
    }
    public int maxsubarray(int[] a){

        int result = 0;
        int temp1[] = new int[a.length];

        int max = 0;
        int temp = 0;
        for(int i = 0; i < a.length; i++){
            if(i == 0){
                max = a[i];
                //System.out.println(max);
                continue;
            }
            else{
                temp = Math.max(a[i],max + a[i]);
                max = temp;
                temp1[i] = max;

            }
            //System.out.println(max);

        }
        for(int i = 0; i < temp1.length; i++){

            result = Math.max(temp1[i], result);
        }
        return result;
    }

}

感觉我用了一个很愚蠢的方法。

发表于 2020-08-19 02:26:28 回复(0)
   public static void test(int[] data) {


        int max_sum = 0;// 最大值
        int count = 0;// 累加和初始化
        for (int i = 0; i < data.length; i++) {
            if (data[i] + count > 0) {
                count += data[i];
                max_sum = Math.max(max_sum, count);//每次累加都更新最大值
            } else {
                count = 0;
            }
            System.out.println(max_sum);
        }


    }

发表于 2020-06-25 19:13:35 回复(0)
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n;
int a[N];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    
    int res = a[0], total = a[0];
    for (int i = 1; i < n; ++i) {
        total = total > 0 ? total + a[i] : a[i];
        res = max(res, total);
    }
    printf("%d\n", res);
    return 0;
}

发表于 2020-06-13 23:23:22 回复(0)
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        int sum = 0;
        int max = 0;
        for(int i = 0; i < arr.length; i++) {
            sum += arr[i];
            sum = sum > arr[i]? sum:arr[i];
            max = sum > max? sum : max;
        }
        System.out.println(max);
    }
}
发表于 2020-05-08 23:06:36 回复(0)
var len=parseInt(readline());
var arr=readline().split(' ').map(Number);
var max=0;
if(arr.length==0){
    console.log(0)
}else if(arr.length==1){
    console.log(arr[0])
}else{
    var tem=0;
    // 关键在于;单个子串的和为负数时,这段子串也就无价值了!!!
    // 然后从下个索引开始计算和,当和>max时就改变max的值,得到最大的值
   for(var i=0;i<len;i++){
       tem+=arr[i];
       if(tem<0){
           tem=0;
       }else if(tem>max){
           max=tem;
       }
   }
   console.log(max)  
}

发表于 2020-04-01 21:13:36 回复(0)
#include<cstdio>
(802)#include<vector>
using namespace std;
vector<int> v;
int main(){
    int n,dp,mmax;
    scanf("%d",&n);
    v.resize(n);
    for(int i=0;i<n;++i){
        scanf("%d",&v[i]);
    }
    mmax=v[0];
    dp=v[0];
    for(int i=1;i<n;++i)
    {
        dp=dp<0?v[i]:(dp+v[i]);
        mmax=max(dp,mmax);
    }
    printf("%d",mmax);
    return 0;
}

发表于 2020-03-23 14:52:51 回复(0)
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int length = sc.nextInt();
        int[] arr=new int[length];
        for(int i=0;i<length;i++){
            arr[i]=sc.nextInt();
        }
        int max=MaxSubseqSum(arr,length);
        System.out.println(max);
        
    }
    
    public static int MaxSubseqSum(int[] arr,int length){
        int thisSum=0;
        int maxSum=0;
        for(int i=0;i<length;i++){
            thisSum+=arr[i];
            if(thisSum>maxSum){
                maxSum=thisSum;
            }else if(thisSum<0){
                thisSum=0;
            }
        }
        return maxSum;
    }
    
}
发表于 2020-01-03 17:54:22 回复(0)
def SubListSum(arr):
    if len(arr) == 0:
        return
    if len(arr) == 1:
        return arr[0]
    maxsum = arr[0]
    maxendsum = arr[0]
    for i in range(1,len(arr)):
        maxendsum = max(arr[i],maxendsum+arr[i])
        maxsum = max(maxsum,maxendsum)
        
    return maxsum

发表于 2019-09-15 15:55:37 回复(0)
N = eval(input())
ls = list(map(int, input().split()))
max_sum = 0 # 最大值
count = 0 # 累加和初始化
for i in range(len(ls)):
    if ls[i]+count > 0:
        count += ls[i]
        max_sum = max(max_sum, count) # 每次累加都更新最大值
    else:
        count = 0
print(max_sum)
最大子列和问题:一次遍历,累加和大于0就一直累加,期间用max函数来选择每次累加后的最大值,当累加和为0或为负值时,重置累加和为0继续遍历
发表于 2019-08-13 16:41:08 回复(0)