首页 > 试题广场 >

求连续子数组的最大和

[编程题]求连续子数组的最大和
  • 热度指数:9307 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
一个非空整数数组,选择其中的两个位置,使得两个位置之间的数和最大。
如果最大的和为正数,则输出这个数;如果最大的和为负数或 0 ,则输出 0

数据范围: ,数组中的值满足

输入描述:
3,-5,7,-2,8


输出描述:
13
示例1

输入

-6,-9,-10

输出

0

这题最操蛋的是,输入竟然是一个字符串,但是又没有说明。

import java.util.*;
/*
数组的子数组最大和问题
从前向后累加,每累加一个判断是否是新的最大值
若累加值<=0,说明左边的数组对右边的数组继续累加没有意义,则重新开始累加
比如1,2,-4,5,6这样一个数组
累加到1时,最大和为1
累加到2时,最大和为3
累加到-4时,结果为-1,最大和仍为3,但由于左边三个数之和为-1,右边的子序列包括这一段不能使和更大,
因此从5开始重新累加
最终最大子序列和为11
*/
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String inputStr = scanner.next();
        String[] inputStrs = inputStr.split(",");
        long sum = 0;
        long max = 0;
        for (String str : inputStrs) {
            long num = Integer.parseInt(str);
            sum += num;
            max = max > sum ? max : sum;
            sum = sum < 0 ? 0 : sum;
        }
        System.out.println(max);
    }
}
编辑于 2020-02-17 12:59:50 回复(2)
比较朴素的做法
#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    string str;
    cin >> str;
    int k;
    vector<int> arr;
    while((k = str.find(',')) != str.npos){
        string temp = str.substr(0, k);
        arr.push_back(stoi(temp));
        str = str.substr(k + 1);
    }
    arr.push_back(stoi(str));
    int tempmax = 0;
    int realmax = arr[0];
    for(int i = 0; i < arr.size(); ++i){
        if(arr[i] <0){
            tempmax = arr[i];
        }
        else{
            tempmax += arr[i];
            if(tempmax <= 0){
                tempmax = arr[i];
            }
        }
        if(tempmax > realmax){
            realmax = tempmax;
        }
    }
    if(realmax <= 0){
        cout << 0 << endl;
    }
    else{
        cout << realmax << endl;
    }
    return 0;
}


编辑于 2020-05-17 12:00:37 回复(0)
a=input().split(',')
maxm=num=0
for j in a:
    num=num+int(j) if num+int(j)>0 else 0#如果当前和非负则保留,为负则舍弃
    maxm=max(maxm,num)
print(maxm)

编辑于 2019-12-26 14:02:52 回复(0)

```java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution17_求连续子数组的最大和 {

public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    String[] line1 = bf.readLine().split(",");
    int[] nums = new int[line1.length];
    for (int i = 0; i < line1.length; i++) {
        nums[i] = Integer.parseInt(line1[i]);
    }
    int max = Integer.MIN_VALUE, cur_sum = 0;
    for (int i = 0; i < nums.length; i++) {
        //如果当前累计的和比0还小,直接抛弃,一个数加上一个负数肯定比原来小,直接取当前数
        if (cur_sum <= 0) {
            cur_sum = nums[i];
        } else {
            cur_sum += nums[i];
        }
        //更新最大值
        if (max < cur_sum) {
            max = cur_sum;
        }
    }
    System.out.println(max > 0 ? max : 0);
}

}```

发表于 2019-08-05 15:09:34 回复(0)
贪心算法,线性时间复杂度
import java.util.*;
public class Main{
    private static Scanner sc;
    public static void main(String[] args){
        sc = new Scanner(System.in);
        while(sc.hasNext()){
            int[] nums = readin();
            int res = nums[0];
            int tmax = nums[0];
            for(int i = 1;i<nums.length;i++){
                tmax = Math.max(tmax+nums[i],nums[i]);
                res = Math.max(res,tmax);
            }
            if(res > 0)
                System.out.println(res);
            else
                System.out.println(0);
        }
    }
    
    private static int[] readin(){
        String[] in = sc.nextLine().split(",");
        int[] res = new int[in.length];
        for(int i = 0;i<in.length;i++)
            res[i] = Integer.parseInt(in[i]);
        return res;
    }
}


发表于 2020-03-04 01:01:49 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int x;
    vector<int> a;
    while(cin>>x){
        a.push_back(x);
        char c = getchar();
        if(c=='\n')
            break;
    }
    int Max=0, s = 0;
    for(int i=0;i<a.size();i++){
        if(s+a[i]<0)
            s = 0;
        else{
            s += a[i];
            Max = max(Max,s);
        }
    }
    cout<<Max<<endl;
    return 0;
}

发表于 2019-11-29 12:43:53 回复(0)

动态规划求解:

int max(int n,int *a)

int sum=0;

int b=0;

for(int i=1;i《n;i++)

if(b》0)

b+=a【i】;

else

b=0;

if(sum《b)

sum=b;

if(sum》0)

printf(sum);

else

printf(0);

发表于 2019-10-12 20:55:29 回复(0)
#include<bits/stdc++.h>
using namespace std;
int main() {
    int ans = 0;
    int sum = 0;
    int tempValue = 0;
    while (~scanf("%d%c",&tempValue))
    {
        sum += tempValue;
        if (sum < 0)
            sum = 0;
        if (sum > ans)
            ans = sum;
    }
    cout << ans<< endl;
}
发表于 2019-10-04 03:24:42 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,sum,maxsum=0;
    vector<int> arr;
    arr.reserve(10000);
    while(scanf("%d,",&n)>0)
        arr.push_back(n);
    sum=arr[0];
    maxsum=max(sum,maxsum);
    for(int i=1;i<arr.size();i++)
        if(sum+arr[i]<0)
            sum=0;
        else{
            sum+=arr[i];
            maxsum=max(maxsum,sum);
        }
    cout<<maxsum;
    return 0;
}

发表于 2019-09-19 21:08:58 回复(0)
"""
最大子段和问题
ans[i]记录以i结尾的最大子段和
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    a = list(map(int, input().strip().split(',')))
    ans = [0]
    temp = 0
    for c in a:
        temp = max(0, temp) + c
        ans.append(temp)
    print(max(ans))

发表于 2019-07-10 12:27:18 回复(0)
x=[int(i) for i in input().split(',')]
res=0
d=max(0,x[0])
res=max(res,d)
fori in range(1,len(x)):
    d=max(d+x[i],0)
    res=max(res,d)
print(res)
编辑于 2018-11-08 00:17:06 回复(1)
package main

import (
    "fmt"
)

func main() {
    var x,sum,max int
    for{
        _,ok:=fmt.Scan(&x)
        if ok!=nil{
            break
        }
        if sum+x<x{
            sum=x
        }else{
            sum+=x
        }
        if sum>max{
            max=sum
        }
    }
    fmt.Print(max)
}

发表于 2023-03-21 12:28:12 回复(0)
const arr =  readline().split(',')
let res = 0
let cur = 0
arr.forEach(str => {
    let num = Number(str)
    if (cur + num < 0) {
        cur = 0
    } else {
        cur += num
        res = Math.max(res, cur)
    }
})
print(res)

发表于 2021-07-18 01:41:12 回复(0)
a1=input().split(',')
a=[]
for n in a1:
    a.append(int(n))
s=0
sumbest=0
for num in a:
    if s+num>0:
        s=s+num
        sumbest=max(s,sumbest)
    else:
        s=0
print(sumbest)
发表于 2021-05-19 20:37:38 回复(0)
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)
import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] ss = s.split(",");
        int[] nums = new int[ss.length];
        
        for(int i = 0; i < ss.length; i++)
            nums[i] = Integer.parseInt(ss[i]);
        
        int ans = maxSum(nums);
        System.out.println(ans);
    }
    
    private static int maxSum(int[] nums){
        
        int max = 0;
        int cur = 0;
        
        for(int num : nums){
            
            cur = Math.max(cur,0);
            cur += num;
            max = Math.max(cur,max);
        }
        return max > 0 ? max : 0;
    }
}

发表于 2020-06-28 00:17:31 回复(0)
import sys

in_num = sys.stdin.readline().strip().split(',')
num = [int(i) for i in in_num]

res = []
for length in range(len(num), 0, -1):
    for i in range(len(num) - length + 1):
        now_num = num[i:i + length]
        res.append(sum(now_num))
final_res = max(res)
if final_res < 0:
    print(0)
else:
    print(final_res)

发表于 2020-06-11 17:19:26 回复(0)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String[] strmun = str.trim().split(",");
    //    System.out.println(""+Arrays.toString(strmun)+" "+strmun.length);
        
        int[] dp=new int[strmun.length];
        
        int i;
        dp[0]=Integer.valueOf(strmun[0]);
        for(i=1;i<strmun.length;i++) {
            
            if(Integer.valueOf(strmun[i])>=(dp[i-1]+Integer.valueOf(strmun[i]))) {
                
                
                dp[i]=Integer.valueOf(strmun[i]);
                
                
            }else {
                
                dp[i]=(dp[i-1]+Integer.valueOf(strmun[i]));
                
                
                
            }
            
            
            
            
        }
        Arrays.sort(dp);
        if(dp[i-1]<=0) {
            System.out.println("0");
            
        }else {
            System.out.println(dp[i-1]);
            
        }
        
        //System.out.println(""+Arrays.toString(dp)+" dp");

    }
}
发表于 2020-05-31 10:29:13 回复(0)
#include<iostream>
(720)#include<vector>

using namespace std;

int main(void){
    string s;
    cin>>s;
    vector<long> v;
    int k;
    while ((k = s.find(',')) != s.npos){
        string temp = s.substr(0, k);
        v.push_back(stol(temp));
        s = s.substr(k+1);
    }
    v.push_back(stol(s));
    vector<long> dp(v.size());
    long MaxAns = 0;
    for (int i = 0; i < v.size(); i++){
        if (i == 0)
            dp[i] = v[i];
        else{
            if (dp[i-1] >= 0)
                dp[i] = dp[i-1] + v[i];
            else
                dp[i] = v[i];
        }
        MaxAns = max(dp[i], MaxAns);
    }
    cout<<MaxAns<<endl;
    return 0;
}

发表于 2020-05-08 16:02:55 回复(0)

测试程序有问题,自测通过但提交未通过

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> vec;
    int num;
    while (cin >> num) {
        vec.push_back(num);
    }
    vector<int> dp(vec.size(), 0);
    dp[0] = vec[0];
    for (int i = 1; i < vec.size(); i++) {
        dp[i] = max(dp[i - 1] + vec[i], 0);
    }
    cout << dp[vec.size() - 1] << endl;
    return 0;
}
编辑于 2020-04-23 22:57:32 回复(0)