最大子段和

给出N个数字, 计算出最大的子段和。

Input

第一行给出一个数字 T(1<=T<=20) 代表接下来的组数.
接下来每 T 行,开始给出一个数组 N(1<=N<=100000), 接着跟着N个数字.

数据保证最后结果小于2^31.

Output

输出最大的字段和



Sample Input
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5


Sample Output
14
7

#include<iostream>

using namespace std;

#define MAX 10001

void vInput(int nN,int nA[]);
int nGetMax(int nN,int nA[]);
void vOutput(int nOut);

int main()
{
    int nCase;
    int nNum;
    int nAns;
    int i;
    int nArr[MAX];

    scanf("%d",&nCase);
    for(i=1;i<=nCase;i++)
    {
        scanf("%d",&nNum);
        vInput(nNum,nArr);
        nAns=nGetMax(nNum,nArr);
        vOutput(nAns);
    }
    return 0;
}

void vInput(int nN,int nA[])
{
    int i;

    for(i=1;i<=nN;i++)
    {
        scanf("%d",&nA[i]);
    }
}

int nGetMax(int nN,int nA[])
{
    int nMax;
    int nCurrentNum;
    int i;

    nCurrentNum=0;
    nMax=0;
    for(i=1;i<=nN;i++)
    {
        
        if(nCurrentNum>=0)
        {
            nCurrentNum+=nA[i];
        }
        else
        {
            nCurrentNum=nA[i];
        }

        if(nMax<nCurrentNum)
            nMax=nCurrentNum;
    }
    return nMax;
}

void vOutput(int nOut)
{
    printf("%d\n",nOut);
}