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

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:

$d(A)=\max_{1\leq s_1\leq t_1<s_2\leq t_2\leq n}\left\{\sum_{i=s_1}^{t_1}a_i+\sum_{j=s_2}^{t_2}a_j\right\}$

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

题意：求两段和最大

一开始自己想

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+,INF=1e9;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int T,n,a[N];

int d[N][],ans;

void dp(){

    ans=-INF;int mx=a[];

    d[][]=a[];d[][]=-INF;

    for(int i=;i<=n;i++){

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

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

        mx=max(mx,d[i][]);

        ans=max(ans,d[i][]);

    }

}

void dp2(){

    ans=-INF;

    for(int i=;i<=n;i++) d[i][]=max(,d[i-][])+a[i];

    d[n+][]=;

    for(int i=n;i>=;i--) d[i][]=max(,d[i+][])+a[i];

    int mx=d[][];

    for(int i=;i<=n;i++){

        ans=max(ans,mx+d[i][]);

        mx=max(mx,d[i][]);

    }

}

int main(int argc, const char * argv[]) {

    T=read();

    while(T--){

        n=read();

        for(int i=;i<=n;i++) a[i]=read();

        dp();

        printf("%d\n",ans);

    }

    return ;

}

巴特西

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

最新文章

热门文章