子数组的最大累加和问题

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

热度指数：2906 时间限制：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

输出

备注:

算法知识视频讲解

Java

牛客332668910号

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)

Java

求offerjava||bigdata

   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)

Java

Mono_Chrome

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)