poj 2479 Maximum sum(dp&最大子段和) - c++编程基础

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:

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

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
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
             //#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 */