最大连续子段和问题

2013年11月8日4,2100

题目描述

给定有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

代码

#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;

}

« 免费馅饼游戏 NOIP2013花匠 »

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

最大连续子段和问题

题目描述

输入

输出

样例输入

样例输出

提示

代码

分类目录

热门文章

Myfriends

近期评论