Given a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below:

Your task is to calculate d(A).

The input consists of T(<=30) test cases. The number of test cases (T) is given in the first line of the input. 

Each test case contains two lines. The first line is an integer n(2<=n<=50000). The second line contains n integers: a1, a2, ..., an. (|ai| <= 10000).There is an empty line after each case.

Print exactly one line for each test case. The line should contain the integer d(A).

In the sample, we choose {2,2,3,-3,4} and {5}, then we can get the answer. 



Huge input,scanf is recommended.

/*

Author: 2486

Memory: 544 KB		Time: 438 MS

Language: C++		Result: Accepted

*/

//题目思路是从左到右分别求出它们所在位置的最大连续和，然后从右到左求出它们所在的最大连续和

//接着就是a[i]+b[i+1],a数组代表着从左到右,b代表着从右到左所以不断的比較a[0]+b[1],a[1]+b[2]求最大值就可以

//如何求解最大值（代码最后段有具体解释）

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=50000+5;

int n,m;

int a[maxn];

int dp[maxn];

int main() {

    scanf("%d",&n);

    while(n--) {

        scanf("%d",&m);

        for(int i=0; i<m; i++) {

            scanf("%d",&a[i]);

        }

        dp[0]=a[0];

        int sum=a[0];

        int ans=a[0];

        for(int i=1; i<m; i++) {

            if(sum<0) {

                sum=0;

            }

            sum+=a[i];

            if(sum>ans) {

                ans=sum;

            }

            dp[i]=ans;

        }

        sum=a[m-1];

        int Max=dp[m-2]+sum;

        ans=a[m-1];

        for(int j=m-2; j>=1; j--) {

            if(sum<0) {

                sum=0;

            }

            sum+=a[j];

            if(sum>ans) {

                ans=sum;

            }

            Max=max(Max,dp[j-1]+ans);

        }

        printf("%d\n",Max);

    }

    return 0;

}

假设当前的数据和小于零。非常明显，将它增加到后面的计算中，肯定会降低最大值

非常easy的道理。-1+4<0+4，假设之前的取值小于零，抛弃它，又一次赋值为零

然后通过maxs不断更新当前的最大值

while(true){

            scanf("%d",&a);

            if(sum<0) {

                sum=0;

            }

            sum+=a;

            if(sum>maxs) {

                maxs=sum;

            }

}