首页 > 代码库 > POJ2479 Maximum sum[DP|最大子段和]

POJ2479 Maximum sum[DP|最大子段和]

2024-08-18 18:45:21   221人阅读

Maximum sum
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 39599 Accepted: 12370

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

1101 -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
题意：求两段和最大
一开始自己想
d[i][0]前i个以i结尾选了一段
d[i][1]前i个以i结尾选了两段
然后扫描维护一个d[i][0]的最大值mx，转移

d[i][0]=max(0,d[i-1][0])+a[i];

d[i][1]=max(d[i-1][1],mx)+a[i];

初始化注意一下就行了

 

还有一种做法：

双向求最大字段和，最后枚举第一段的结束位置求

//两个dp函数，两种方法#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int N=5e4+5,INF=1e9;inline int read(){    char c=getchar();int x=0,f=1;    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}    return x*f;}int T,n,a[N];int d[N][2],ans;void dp(){    ans=-INF;int mx=a[1];    d[1][0]=a[1];d[1][1]=-INF;    for(int i=2;i<=n;i++){        d[i][0]=max(0,d[i-1][0])+a[i];        d[i][1]=max(d[i-1][1],mx)+a[i];        mx=max(mx,d[i][0]);        ans=max(ans,d[i][1]);    }}void dp2(){    ans=-INF;    for(int i=1;i<=n;i++) d[i][0]=max(0,d[i-1][0])+a[i];    d[n+1][1]=0;    for(int i=n;i>=1;i--) d[i][1]=max(0,d[i+1][1])+a[i];    int mx=d[1][0];    for(int i=2;i<=n;i++){        ans=max(ans,mx+d[i][1]);        mx=max(mx,d[i][0]);    }}int main(int argc, const char * argv[]) {    T=read();    while(T--){        n=read();        for(int i=1;i<=n;i++) a[i]=read();        dp();        printf("%d\n",ans);    }        return 0;}

 

POJ2479 Maximum sum[DP|最大子段和]


联系
我们