两个不相连的子数组最大值

F  Maximum sum

Accept:18	Submit:42
Time Limit:1000MS	Memory Limit:65536KB

Description

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

d(A)=sum{a[s1]~a[t1]}+sum{a[s2]~a[t2]}

The rule is 1<=s1<=t1

Your task is to calculate d(A).

Input

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.

Output

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

Sample Input

1

 

10

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

Sample Output

13

Hint

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

Huge input,scanf is recommended.

思路：

1. 从左到右求最大子数组和

2. 从右到左求最大子数组和

3. 利用1,2的结果得到两个子数组的最大和

#include <stdio.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b))

int n;
int data[50001];
int left_max[50001];
int right_max[50001];

void dp_max(int *data, int *max_arr)
{
    int i = 0;
    int sum = 0;
    sum = max_arr[0] = data[0];
    for (i=1; i<n; i++)
    {
        sum = MAX(sum + data[i], data[i]);
        max_arr[i] = MAX(sum, max_arr[i-1]);
    }
}

void reverse_arr(int *data)
{
    int size = n;
    int front = 0;
    int tail = n - 1;
    int tmp = 0;

    while (tail - front > 0)
    {
        tmp = data[front];
        data[front] = data[tail];
        data[tail] = tmp;
        tail--;
        front++;
    }
}

void printOut(int *max_arr)
{
    int i;
    for (i=0; i<n; i++)
        printf("%d, ", max_arr[i]);
    printf("\n");
}

int handle()
{
    dp_max(data, left_max);
    //printOut(left_max);
    reverse_arr(data);
    dp_max(data, right_max);
    //printOut(right_max);

    int i = 0;
    int tmp = 0;
    int max = left_max[0] + right_max[n-2];
    for (i=1; i<n-1; i++)
    {
        tmp = left_max[i] + right_max[n-2-i];
        if (tmp > max)
            max = tmp;
    }

    return max;
}

int main()
{
    int T = 0;
    int i = 0;
    int j = 0;
    int ret = 0;

    scanf("%d", &T);
    for (i=0; i<T; i++)
    {
        scanf("%d", &n);
        for (j=0; j<n; j++)
            scanf("%d", &data[j]);
        ret = handle();
        printf("%d\n", ret);
    }
}