|
Maximum sum
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
|
题意：
给你n个数字的序列。叫你找出两个连续子段。两子段不重合。使得两字段中所有数字的和最大。
思路：
开始因为没注意到不重合WA了数次！解法还是蛮简单的。从前往后和从后往前分别做一次最大子段和。然后枚举分段点。就可以得到答案了。
详细见代码：
#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>
//#pragma comment(linker,"/STACK:1024000000,1024000000")
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
*/