首页 > 试题广场 >

连续最大和

[编程题]连续最大和
  • 热度指数：59208 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3

输入描述:
输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。


输出描述:
所有连续子数组中和最大的值。
示例1

输入

3
-1 2 1

输出

3
算法知识视频讲解
添加回答
蓝魔4头像 蓝魔4 
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> in(n);
    for(int i=0;i<n;i++)
        cin>>in[i];
    vector<int> dp(n);
    dp[0]=in[0];
    int maxVal=in[0];
    for(int i=1;i<n;i++)
    {
        dp[i]=max(in[i],dp[i-1]+in[i]);
        if(dp[i]>maxVal)
            maxVal=dp[i];
    }
    cout<<maxVal<<endl;
    return 0;
}

发表于 2017-08-08 17:12:51 回复(2)
Java
牛客753137号头像 牛客753137号 
//本题用动态规划可解，唯一的疑问是多个32位的int型元素相加有可能溢出啊，但是测试数据还是通过了
//估计出题人默认了连结果都是int型的
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int [] a = new int [n];
        for(int i=0; i<n; ++i){
            a[i] = in.nextInt();
        }
        
        int res = maxSum(a,n);
        System.out.println(res);
           
    }
    
    public static int maxSum(int[] a,int n){

        if(a.length == 0) return 0;
        //记录前k个元素中的子数组最大和
		int max = Integer.MIN_VALUE;
        //记录以当前元素结尾的连续子数组最大和
        int curMax = 0;
        for(int i=0; i<n; ++i){
			if(curMax <= 0){
                curMax = a[i];
            }
            else{
                curMax += a[i];
            }
            if(max < curMax){
                max = curMax;
            }
        }  
        return max;
    }
}

发表于 2017-08-19 09:59:02 回复(6)
C/C++
Misaki丶Fx头像 Misaki丶Fx 
#include <iostream>
#include <limits.h>
using namespace std;
int main()
{
    int num = 0;
    cin >> num;
    int curMax = 0;
    int max = INT_MIN;
    for(int i = 0; i < num; i++)
    {
        int temp = 0;
        cin >> temp;
        curMax += temp;
        if(curMax > max)
        {
            max = curMax;
        }
        if(curMax < 0)
        {
            curMax = 0;
        }
    } 
    cout << max << endl;
}
一开始理解错了题意，做成了求最大数值连续的子序列的最大值，恍然大悟发现，这题连数组都用不着建
发表于 2019-05-24 01:20:49 回复(0)
tw-luo头像 tw-luo 
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n;
    int max = -1e5, now = 0,m;
    cin >> n;
    vector<int> a;
    for (int j = 0; j < n; j++)
    {
        cin >> m;
        a.push_back(m);
    }
    for (int j = 0; j < n;j++)
    {
        now += a[j];
        if (now>max)
            max = now;
        if (now < 0)
            now = 0;
    }
    cout << max<<endl;
    return 0;
}

发表于 2019-04-13 21:14:59 回复(0)
PPheng头像 PPheng 
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    int n;
    int a[120000];
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int ans=a[1];//初始化一下
    int t=a[1];
    for(int i=2;i<=n;i++)
    {
        if(t>=0)
        t+=a[i];
        
        else
        t=a[i];
        
        ans=max(ans,t);
    }
    cout<<ans<<endl;
    
    
    return 0;
}
这道题是一道很经典的题目，可以设一个sum[i]数组表示从一到i个数的和进行dp，也可以贪心，贪心的方法很简单易懂。
不妨这么想：对于一个子串，如果他的下一个数是正数，那么这个字串加上这个正数一定比原来的大。如果是负数，那么一定比原来的小，0的话对字串没有影响。
所以假设一下原来的子串是最大的，他加上一个正数后就成为了新的最大字串。如果加上负数就比原来的小了，所以原来的依然是正解。那么答案就出来了，如果下一个数大于等于0就一直加下去，是负数的话就停止加，把这个数赋值给t，让它成为一个新的字串继续这个过程，ans一直保存的最大值，最后输出ans就可以了。这样只需要遍历一遍，可以应对很大的数据范围。
（第一次发题解，有表达不当之处，感谢各位斧正）
发表于 2018-10-27 23:27:02 回复(0)
🎧关键词、头像 🎧关键词、

这题贼奇怪，全负数竟然不输出0，而是输出最大的负数。所以还得判断全负数的情况。

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        while(s.hasNext()){
            int n = s.nextInt();
            int[] a = new int[n];
            for(int i=0;i<n;i++){
                a[i]=s.nextInt();
            }
            int maxSum = 0;
            int thisSum = 0;
            int count = 0;//计负数的个数，判断是否为全负数
            int maxOfnegative = Integer.MIN_VALUE;//表示负数中最大的负数
            for(int i=0;i<n;i++){
                if(a[i]<0){
                    count++;
                    if(a[i]>maxOfnegative){
                        maxOfnegative = a[i];
                    }
                }
                thisSum+=a[i];
                if(thisSum>maxSum){
                    maxSum=thisSum;
                }else if(thisSum<0){
                    thisSum = 0;
                }
            }
            if(count==n){//表示全为负数，输出最大的负数
                System.out.println(maxOfnegative);
            }else{
                System.out.println(maxSum);
            }
        }
    }
}
发表于 2018-08-20 23:36:15 回复(0)
Fizzz头像 Fizzz
考察前面和对之后是否有贡献
#include <iostream>

using namespace std;

int main()
{
    int n ;

    while (cin >>n)
    {
        int mmax = 0xffffffff;
        int a[100001] = { 0 };
        for (int q = 0; q < n; ++q)
        {
            cin >> a[q];
        }
            int dp[100000] = { 0 };    dp[1] = a[0];

            for (int i = 1; i < n; ++i)
            {
                dp[i + 1] = max(a[i], dp[i] + a[i]);
                if (mmax < dp[i + 1])mmax = dp[i + 1];
            }
        cout <<mmax<< endl;
    }
    return 0;
}
发表于 2018-07-13 11:33:10 回复(0)
bangrepeng头像 bangrepeng
要求最大的，那么就不要加负数，即每当前面累加的总和为负数的时候，把前面加的全部清零，重新加，重新计算！每加一个数都与之前的和比较，变大了，就记录更大的和，得到的是最大的那个和！
如果遇到负数：（1）如果前面累加的和是负数，和已被清零，加的是负数，又被清零；（2）前面和如果是正数，加这个负数必然更小，暂时不会更新最大值，且看下次加的是不是比现在这个负数要大再决定是否更新（因为负数不够小，那么前面的正数和对后面还是有贡献的）；只有当加了一个非常大的负数，把前面的正的和都抵消还有余，使得总和为负，那么加这个大的负数就没有意义了，故清零。
非常好的思路！
发表于 2018-06-23 16:38:32 回复(0)
深度学习ing的人头像 深度学习ing的人 

	#include <stdio.h>





	#include <stdlib.h>





	intmain()





	{





	    intlen=0, iIndex=0;





	    int*pData = NULL;





	    scanf("%d", &len);





	    if(len<=0)return-1;





	    pData = (int*)malloc(sizeof(int)*len);





	    for(iIndex=0; iIndex<len; ++iIndex)





	        scanf("%d", &pData[iIndex]);





	    intmaxSum = pData[0];





	    intnCurSum = pData[0];





	    for(inti=0; i<iIndex; ++i)





	    {





	        if(nCurSum<=0)





	            nCurSum = pData[i];





	        else





	            nCurSum += pData[i];





	        if(nCurSum > maxSum)





	            maxSum = nCurSum;





	    }





	    printf("%d", maxSum);





	    return0;





	}

发表于 2018-06-10 22:22:56 回复(0)
C/C++
dv_vd头像 dv_vd
#include <iostream>
#include<limits.h>
using namespace std;

int main() {
    int n, m;
    int sum = 0;
    int max = INT_MIN;
    cin >> n;
    while (n--)
    {
        cin >> m;
        sum += m;
        if (sum > max)
            max = sum;
        if (sum < 0)
            sum = 0;
    }
    cout << max << endl;
    return 0;
}
发表于 2018-04-01 22:21:59 回复(0)
Java
李狗什么头像 李狗什么
//动态规划
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int temp = 0;
        int max = Integer.MIN_VALUE;
        int num = sc.nextInt();
        for(int i = 0;i<num;i++){
            int val = sc.nextInt();
            temp = Math.max(temp+val,val);
            if(temp>max){
                max = temp;
            }
        }
        System.out.println(max);
    }
}
发表于 2018-03-24 16:02:15 回复(0)
NarcissusAbyss头像 NarcissusAbyss 
/*
dp保存的是某一段连续的和，当dp[i]+v[i]<0时，证明v[i]已经不能取了，那么dp[i+1]重新
置0，如果大于0，证明v[i]还可能可以取，然后用m来找最大值。全部为负数的解决办法是用
m=max(v[i], m)来找负数里面的最大值。
*/
#include <iostream>
#include <vector>
using namespace std;

int sum(vector<int> &v) {
    vector<int> dp(v.size() + 1, 0);
    int m = -1e9;
    for(int i = 0; i < v.size(); i ++) {
        if(dp[i] + v[i] < 0) {
            dp[i + 1] = 0;
            m = max(v[i], m);
        }
        else {
            dp[i + 1] = dp[i] + v[i];
            m = max(dp[i + 1], m);
        }
    }
    return m;
}

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; i ++) {
        cin >> v[i];
    }
    cout << sum(v) << endl;
}

发表于 2018-03-23 22:40:56 回复(0)
ACpeppermint头像 ACpeppermint 













	#include <iostream>





	#include <algorithm>





	 





	using namespace std;





	 





	const int maxn = 1e5 + 7;





	int p[maxn];





	int sum[maxn];





	 





	int sum_max(int len) {





	    int res = -1;





	    sum[0] = p[0];





	    for(int i = 1; i < len; i++) {





	        sum[i] = max(sum[i - 1] + p[i], p[i]);





	        res = max(sum[i], res);





	    }





	    return res;





	}





	 





	int main()





	{





	    int n;





	    cin >> n;





	    for(int i = 0; i < n; i++) {





	        cin >> p[i];





	    }





	    cout << sum_max(n) << endl;





	    return 0;





	}

发表于 2017-09-14 13:54:30 回复(0)
有人＠你头像 有人＠你 
#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char const *argv[])
{
	int n;
	cin>>n;
	vector<int> vec(n);
	for(int i=0;i<n;i++){
		cin>>vec[i];
	}
	vector<int> dp(n);
	dp[0]=vec[0];
	int res=vec[0];
	for(int i=1;i<n;i++){
		dp[i]=max(dp[i-1]+vec[i],vec[i]);
        res=max(dp[i],res);
	}
	cout<<res<<endl;
	return 0;
}

编辑于 2017-09-05 21:03:26 回复(0)
Elham头像 Elham 
 import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int[] a = new int[n];
            
            a[0] = sc.nextInt();
            int max=a[0];
            
            for(int i=1;i<n;i++){
                a[i] = sc.nextInt();
                if( a[i-1]>=0 ){
                    a[i] = a[i-1]+a[i];
                }
                if( max<a[i] ){
                    max = a[i];
                }
            }
            
            System.out.println(max);
            
        }
        sc.close();
    }
}
发表于 2017-09-05 11:36:42 回复(0)
一条大咸鱼...头像 一条大咸鱼... 
#include <iostream>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        bool flag=false;
        int *list=new int[n];
        for(int i=0;i<n;i++){
            cin>>list[i];
            if(list[i]>0)
                flag=true;
        }
        int count=0;
        int max=0;
        if(flag){
                    for(int i=0;i<n;i++){
            count+=list[i];
            if(count<0){
                count=0;
            }
            if(max<count){
                max=count;
            }
        	}
        }
        else{
            max=list[0];
            for(int i=0;i<n;i++){
                if(list[i]>max)
                    max=list[i];
            }
        }
        cout<<max<<endl;
    }
}

发表于 2017-08-21 16:13:10 回复(0)
C/C++
骏博日博的迷弟头像 骏博日博的迷弟
最经典的dp 

#include <cstdio>
#include <algorithm>
int dp[100001], x[100001];
int main()
{
	int n;
	while (scanf("%d", &n) != EOF)
	{
		for (int i = 0; i<n; i++)
		{
			scanf("%d", x + i);
		}
		dp[0] = x[0];
		long long max_ans = dp[0];
		for (int i = 1; i<n; i++)
		{
			dp[i] = std::max(x[i], dp[i - 1] + x[i]);
			if(dp[i]>max_ans)
                max_ans = dp[i];
		}
		printf("%lld\n", max_ans);
	}
	return 0;
}

发表于 2017-08-08 20:30:08 回复(0)
美团到店招聘头像 美团到店招聘
//思路：对于第i个元素，它要么是新连续子数组的开头，要么加入之前还未结束的连续字符数组
所以buf[i] = max(buf[i-1]+input[i],input[i]);其中，input[]是输入数组

#include <stdio.h>
//#include <stdlib.h>
#include <algorithm>
using namespace std;
intmain(){
    intn;
    scanf("%d",&n);
    if(n <= 0)
        return0;
    int* input = newint[n];
    for(inti = 0;i<n;++i)
        scanf("%d",&input[i]);
    //处理过程
    int* buf = newint[n];
    buf[0] = input[0];
    for(inti = 1;i<n;++i){
        if(buf[i-1]+input[i] > input[i])
            buf[i] = buf[i-1]+input[i];
        else
            buf[i] = input[i];
    }
    sort(buf,buf+n);
    printf("%d",buf[n-1]);   
    return0;
}
发表于 2017-02-07 22:38:27 回复(0)
牛客2793674号头像 牛客2793674号 
动态规划问题 
设dp[i]表示以第 i个元素为结尾的连续子数组的最大和，则递推方程式为 dp[i]=max{dp[i-1]+a[i], a[i]};
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan=new Scanner(System.in);
		int n;
		while(scan.hasNextInt()){
			n=scan.nextInt();
			int[] array=new int[n];
			for(int i=0;i<n;i++)
				array[i]=scan.nextInt();
			
			int[] dp=new int[n];
			dp[0]=array[0];
			int max=array[0];
			for(int i=1;i<n;i++){
				if(dp[i-1]+array[i] > array[i])
					dp[i]=dp[i-1]+array[i];
				else
					dp[i]=array[i];	
				if(dp[i]>max)
					max=dp[i];
			}
			System.out.println(max);
		}
	}

}

发表于 2017-03-12 21:44:01 回复(1)
yangxiaorong头像 yangxiaorong
var count=read_line();
var numbers=read_line();
var array=numbers.split("");
var max_sum=0;
max_sum=array[0];
var arr2=[];
for(var i=1;i<array.length;i++){
  // max_sum+=array[i];
    if(array[i]>array[i-1]+max_sum){ 
         max_sum=array[i];
        arr2.push(max_sum);
    }
    else{
        max_sum+=array[i];
        arr2.push(max_sum);
    }
}
arr2.sort(function(a,b){
    returnb-a;
});
console.log(arr2[0]);
我写了html文档自己定义一个数组测试时对的啊,但是这里就是怎么都运行不了,哪位大神知道在牛客网上js编程怎么获取输入的字符串吗?
发表于 2016-12-29 20:50:02 回复(2)
提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 滴滴 贪心 动态规划 Java工程师
上传者：小小
难度：
222条回答 25009浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号