求连续子数组的最大和

[编程题]求连续子数组的最大和

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

一个非空整数数组，选择其中的两个位置，使得两个位置之间的数和最大。

如果最大的和为正数，则输出这个数；如果最大的和为负数或 0 ，则输出 0

数据范围： $1 \le n \le 10000 \$ ，数组中的值满足 $|val| \le 10000 \$

输入描述:

3,-5,7,-2,8

输出描述:

示例1

输入

-6,-9,-10

输出

算法知识视频讲解

Java

刘晓雪liuxiaoxue

import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String inputStr = sc.next();
String[] inputStrs = inputStr.split(",");
long cur = 0;
long maxSum = Integer.MIN_VALUE;
for(String str : inputStrs){
long num = Integer.parseInt(str);
cur = Math.max(cur + num, num);
maxSum = Math.max(maxSum, cur);
}
long res = maxSum > 0 ? maxSum : 0;
System.out.println(res);
}
}

发表于 2020-10-11 17:07:26 回复(0)

Java

火猿

import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String inPut = scanner.nextLine();
String[] arr = inPut.split(",");
int max = 0;
for(int i = 0; i < arr.length; i++){
for(int j = arr.length -1; j >= i; j--){
int num = Integer.valueOf(arr[i]);
if(j == i){
if(max < num)
max = num;
}else{
int sum = 0;
for(int k = i; k <= j - i; k++){
sum += Integer.valueOf(arr[k]);
}
if(max < sum)
max = sum;
}
}
}
System.out.println(max);
}
}

发表于 2019-09-09 20:41:49 回复(0)

Java

我只想安心搬砖

dp的方法。递推的公式，dp[i]表示以下标i结尾的子数组最大和，所以递推式就是

dp[i]=max(dp[i-1]+a[i],a[i])

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.nextLine();
            String[] split = s.split(",");
            int[] a = new int[split.length];

            for (int i = 0; i < a.length; i++) {
                a[i] = Integer.parseInt(split[i]);

            }


            int[] dp = new int[a.length];
            dp[0] = a[0];
            for (int i = 1; i < a.length; i++) {
                dp[i] = Math.max(dp[i - 1] + a[i], a[i]);
            }
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < a.length; i++) {
                if (dp[i] > max)
                    max = dp[i];
            }
            System.out.println(max > 0 ? max : 0);
        }

    }

}

发表于 2019-08-15 22:28:02 回复(0)

Java

lenfranky

import java.io.*;
import java.util.*;

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

发表于 2019-08-09 21:15:26 回复(0)

Java

超越姐姐保佑我i

import java.util.Scanner;

public class Main {
    public static int getSum(int[] arr) {
        //check arr
        if(arr == null || arr.length <= 0) 
            return 0;
        
        int curSum = 0;
        int maxSum = Integer.MIN_VALUE;
        
        for(int i=0; i<arr.length; i++) {
            if(curSum < 0) {
                curSum = arr[i];
            } else {
                curSum += arr[i];
            }
            
            if(curSum > maxSum) {
                maxSum = curSum;
            }
        }
        
        return maxSum > 0 ? maxSum : 0;
    }
    
    public static void main(String[] args) {
        Scanner sc  = new Scanner(System.in);
        String[] arrStr = sc.nextLine().split(",");
        int[] arr = new int[arrStr.length];
        for(int i=0; i<arr.length; i++)
            arr[i] = Integer.valueOf(arrStr[i]);
        
        int result = getSum(arr);
        System.out.println(result);
    }
    
}

发表于 2018-11-06 22:54:06 回复(0)

Java

张子寒

先合并相邻的正数、相邻的负数，再遍历所有情况

import java.util.*;

public class Main{
    public static void main(String [] args){
        Scanner sc  = new Scanner(System.in);
        String[] arrstr = sc.nextLine().split(",");
        int [] arr = new int[arrstr.length];
        for(int i = 0; i < arr.length; i ++)
            arr[i] = Integer.valueOf(arrstr[i]);
        
        int top = arr.length - 1;
        
        for(int i = 0; i < top; i ++){
            if( arr[i] == 0 || arr[i+1] == 0 ||
               ( arr[i] < 0 ) == ( arr[i+1] < 0 ) ){
                arr[i] += arr[i + 1];
                System.arraycopy(arr, i+2, arr, i+1, top-i-1);
                top --;
                i --;
            }
        }
        int[] tmp = new int[top+1];
        System.arraycopy(arr, 0, tmp, 0, top+1);
        System.out.println(func(tmp, 0, 0));
    }      private static int max = 0;
     private static int func(int[] arr, int sum, int index){    if( index == arr.length )    return max;    max = max >= arr[index] ? max : arr[index];      sum += arr[index];    max = max >= sum ? max : sum;      func(arr, sum, index+1);    func(arr, 0, index+1);    return max;    }
}