/*Maximum sumTime Limit: 1000MS		Memory Limit: 65536KTotal Submissions: 29822		Accepted: 9123DescriptionGiven a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below:Your task is to calculate d(A).InputThe 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.OutputPrint exactly one line for each test case. The line should contain the integer d(A).Sample Input1101 -1 2 2 3 -3 4 -4 5 -5Sample Output13HintIn the sample, we choose {2,2,3,-3,4} and {5}, then we can get the answer.Huge input,scanf is recommended.SourcePOJ Contest,Author:Mathematica@ZSU*/#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int n = 0, a[50005] = {0}, dp1[50005] = {0}, dp2[50005] = {0};int m1[50005] = {0}, m2[50005] = {0};void solve(){    dp1[0] = a[0];    m1[0] = a[0];    for(int i = 1; i < n; ++i)    {        dp1[i] = (a[i] > dp1[i - 1] + a[i]) ? a[i] : (dp1[i - 1] + a[i]);        m1[i] = (m1[i - 1] > dp1[i]) ? m1[i - 1] : dp1[i];    }    dp2[n - 1] = a[n - 1];    m2[n - 1] = a[n - 1];    for(int i = n - 2; i >= 0; --i)    {        dp2[i] = (a[i] > dp2[i + 1] + a[i]) ? a[i] : (dp2[i + 1] + a[i]);        m2[i] = (m2[i + 1] > dp2[i]) ? m2[i - 1] : dp2[i];    }}int main(){    int t = 0;    scanf("%d", &t);    for(int i = 0; i < t; ++i)    {        scanf("%d", &n);        memset(dp1, 0, sizeof(dp1));        memset(dp2, 0, sizeof(dp2));        memset(m1, 0, sizeof(m1));        memset(m2, 0, sizeof(m2));        for(int j = 0; j < n; ++j)            scanf("%d", &a[j]);        solve();        int m = -10000000;        for(int j = 0; j < n - 1; ++j)        {            if(m < m1[j] + m2[j + 1])                m = m1[j] + m2[j + 1];        }        printf("%d\n", m);    }    return 0;}