最大连续子串和问题

2013年11月28日3,3300

题目描述

给定有n个整数(可能为负整数)组成的序列a1,a2,…,an,求该序列连续的子段和的最大值。如果该序列的所有元素都是负整数时定义其最大子段和为0。例如，当(a1,a2,a3,a4,a5)=(-5,11,-4,13,-4-2)时，最大子段和为11+(-4)+13=20。

输入

输入数据有T组测试数据。测试数据的数目 (T)在输入的第一行给出。每组测试数据有两行：第一行整数个数N，第二行为N个整数，每个整数之间用一空格隔开。

输出

对于每组数据，输出一行，为最大连续子段和。

样例输入

1 6 -5 11 -4 13 -4 -2

样例输出

提示

1<=T<=20
1<=N<=100000

N个整数的范围为-1000到1000

来源

dp做法

#include<iostream>

#include<cstring>
using namespace std;
int main()
{
    int m,n,a[100001];
    int f[100001],Max;
    cin>>m;
    for(int k=1;k<=m;k++)
    {
        Max=0,n=0;
        memset(a,0,sizeof(a));
        memset(f,0,sizeof(f));
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            if(f[i-1]>f[i])f[i]=f[i-1];
            f[i]+=a[i];
            if(f[i]>Max)Max=f[i];
        }
        cout<<Max<<endl;
    }
    return 0;
}

#include<iostream>

#include<cstring>

using namespace std;

int main()

{

int m,n,a[100001];

int f[100001],Max;

cin>>m;

for(int k=1;k<=m;k++)

{

Max=0,n=0;

memset(a,0,sizeof(a));

memset(f,0,sizeof(f));

cin>>n;

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

{

cin>>a[i];

if(f[i-1]>f[i])f[i]=f[i-1];

f[i]+=a[i];

if(f[i]>Max)Max=f[i];

}

cout<<Max<<endl;

}

return 0;

}

还有O(n)的

#include<iostream>
using namespace std;
int main()
{
	int n,s=0,x,ans=0;
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		cin>>x;
		s+=x;
		ans=max(ans,s);
		if(s<0)s=0;
	}
	cout<<ans;
	return 0;
}

#include<iostream>

using namespace std;

int main()

{

int n,s=0,x,ans=0;

cin>>n;

for(int i=2;i<=n;i++)

{

cin>>x;

s+=x;

ans=max(ans,s);

if(s<0)s=0;

}

cout<<ans;

return 0;

}

« NOIP2007守望者的逃离 NOIP2002过河卒 »

hzwer.com _ Home | http://hzwer.com

最大连续子串和问题

题目描述

输入

输出

样例输入

样例输出

提示

来源

分类目录

热门文章

Myfriends

近期评论