Maximum sum

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 44459		Accepted: 13794

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

和poj2593几乎一样。
https://www.cnblogs.com/Weixu-Liu/p/10512447.html
C++代码：

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

using namespace std;

const int maxn = ;

int a[maxn],dpl[maxn],dpr[maxn],m1[maxn],m2[maxn];

int Inf = -0x3f3f3f3f;

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        int n;

        scanf("%d",&n);

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

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

        }

        memset(dpl,,sizeof(dpl));

        memset(dpr,,sizeof(dpr));

        m1[] = m2[n+] = Inf;

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

            dpl[i] = max(dpl[i-] + a[i],a[i]);

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

                m1[i] = dpl[i];

            else

                m1[i] = m1[i-];

        }

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

            dpr[i] = max(dpr[i+] + a[i],a[i]);

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

                m2[i] = dpr[i];

            else

                m2[i] = m2[i+];

        }

        int maxsum = Inf;

        int tmp[maxn];

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

            tmp[i] = m1[i] + m2[i+];

            if(maxsum < tmp[i])

                maxsum = tmp[i];

        }

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

    }

    return ;

}