Maximum sum

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 39089		Accepted: 12221

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).

1

10

1 -1 2 2 3 -3 4 -4 5 -5

13

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

Huge input,scanf is recommended.

 //2016.8.21

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int N = ;

 const int inf = 0x3f3f3f3f;

 int a[N], dpl[N], dpr[N];//dpl[i]表示从左往右到第i位的最大子段和,dpr[i]表示从右往左到第i位的最大子段和

 int main()

 {

     int T, n;

     cin>>T;

     while(T--)

     {

         scanf("%d", &n);

         for(int i = ; i < n; i++)

         {

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

         }

         memset(dpl, , sizeof(dpl));

         memset(dpr, , sizeof(dpr));

 //从左往右扫

 //*************************************************

         dpl[] = a[];

         for(int i = ; i < n; i++)

             if(dpl[i-]>) dpl[i] = dpl[i-]+a[i];

             else dpl[i] = a[i];

         for(int i = ; i < n; i++)

             if(dpl[i]<dpl[i-])

                   dpl[i] = dpl[i-];

 //从右往左扫

 //*************************************************

         dpr[n-] = a[n-];

         for(int i = n-; i>=; i--)

             if(dpr[i+]>) dpr[i] = dpr[i+]+a[i];

             else dpr[i] = a[i];

         for(int i = n-; i>=; i--)

             if(dpr[i]<dpr[i+])

                   dpr[i] = dpr[i+];

 //*************************************************

         int ans = -inf;

         for(int i = ; i < n-; i++)

         {

             ans = max(ans, dpl[i]+dpr[i+]);

         }

         cout<<ans<<endl;

     }

     return ;

 }