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\n",max);
    }
    return 0;
}
      

杭電1003的改編題~代碼改改就行了~