poj-2479 Maximum sum 【最大字串和】

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/44081955

Maximum sum

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 34697		Accepted: 10752

Description

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

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.

Source

POJ Contest
,Author:Mathematica@ZSU

求两段的最大和，前后进行两次dp；

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>

using namespace std;

int t, n, p[100010], ans[100010];

int main()
{
    scanf("%d",&t);
    while (t--)
    {
        memset(ans,0,sizeof(ans));
        scanf("%d",&n);
        int b = 0, sum = -1000000000;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &p[i]);
            b += p[i];
            sum = max(b, sum);
            ans[i] = sum;
            if (b < 0) 
                b = 0;    
        }

        b = 0, sum = -1000000000;
        int tmp = -1000000000;

        for (int i = n - 1; i >= 1; i--)
        {
            b += p[i];
            sum = max(b, sum);
            tmp = max(tmp, ans[i - 1] + sum);
            if (b < 0) 
                b = 0;
        }
        printf("%d\n",tmp);
    }
    return 0;
}