1142 NOJ 最大连续和

最大连续和

时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 1127 测试通过 : 208

题目描述

给出一个长度为n的序列A1，A2，…，An，求最大的连续和。要求找到1≤i≤j ≤n，使得Ai+Ai+1+…+Aj尽量大。

输入

第1行输入一个正整数n（n≤1000），此后输入n行，每行给出一个测试用例，包含正整数m和m个整数，以空格分隔各个数。

输出

输出n行。对于每一个测试用例，在一行输出最大的连续和。

样例输入

2
3 1 -1 3
3 1 2 3

样例输出

3
6

实现代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<limits.h>
using namespace std;
int main()
{
   // freopen("data.in","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int *num=new int[n+2];
        for(int i=1;i<=n;i++)
            scanf("%d",&num[i]);
        int sum=0,max=INT_MIN;//因为可能都是负数，所以设置初始max尽可能的小
        for(int i=1;i<=n;i++)
        {
            if(sum>=0)
                sum+=num[i];//如果之前的和大于等于0，继续加
            else
            {
                sum=num[i];//否则，舍弃前面所有的数据，从这一项开始
            }
            if(sum>max)
            {
                max=sum;
            }
        }
        printf("%d
",max);
    }
    return 0;
}

杭电1003的改编题~代码改改就行了~