POJ2479 Maximum sum

POJ2479 Maximum sum

Description

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.

题意是给出一个序列，求出这个序列中两个不相交子串的和最大。

这是一道与POJ2593相似的DP题，但这一道的数据感觉很水。

做法是dp[i]代表1到i的子串最大和。然后逆向求最大和，答案便是max(ans,dp[i-1]+Max)

就是相当于在序列中画一条分界线，左边的最大和和右边的最大和相加最大

代码如下：

#include#include#include#includeusing namespace std;#define N 50010 int a[N],dp[N];int main(){ int i,j,n,m,T; scanf("%d",&T); while(T--) { int cnt=0; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&a[i]);if(a[i]<0) cnt++;} if(cnt==n){ sort(a+1,a+1+n); printf("%d\n",a[n]+a[n-1]); continue; } dp[0]=a[1]; int Max=-100001,sum=0; for(i=1;i<=n;i++) { sum+=a[i]; dp[i]=max(sum,dp[i-1]); if(sum>Max){ dp[i]=sum; Max=sum; } if(sum<=0){ sum=0; dp[i]=dp[i-1]; } } //for(i=1;i<=n;i++) cout<=2;i--) { sum+=a[i]; if(sum>Max) { Max=sum; ans=max(ans,dp[i-1]+Max); } if(sum<=0) sum=0; } printf("%d\n",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。