## poj 2479 Maximum sum(dp&最大子段和)

2019年04月13日 算法 ⁄ 共 1598字 ⁄ 字号 评论关闭
Maximum sum
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 31468 Accepted: 9665

Description

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

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

```#include<algorithm>
#include<iostream>
#include<string.h>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
using namespace std;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double PI=acos(-1.0);
const int maxn=50100;
int dpl[maxn],dpr[maxn],ml[maxn],arr[maxn];
int main()
{
int t,n,i,ans;

scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
ans=-INF;
dpl[0]=dpr[n+1]=ml[0]=0;
for(i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
dpl[i]=max(arr[i],arr[i]+dpl[i-1]);//从前往后
ans=max(ans,dpl[i]);
ml[i]=ans;//记录到i时的最大字段和
}
ans=-INF;//必须要再次初始化。开始偷懒认为死一样的。结果会导致最后只有一个字段。数据见下
for(i=n;i>1;i--)
{
dpr[i]=max(arr[i],arr[i]+dpr[i+1]);
ans=max(ans,ml[i-1]+dpr[i]);
}
printf("%d\n",ans);
}
return 0;
}
/*
1
10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
*/
```