最大子段和 模板题 51Nod 1049

N个整数组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续子段和的最大值。当所给的整数均为负数时和为0。

例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。

Input

第1行：整数序列的长度N（2 <= N <= 50000)

第2 - N + 1行：N个整数（-10^9 <= A[i] <= 10^9）

Output

输出最大子段和。

Input示例

6

-2

11

-4

13

-5

-2

Output示例

20
给一组数据：http://paste.ubuntu.com/25117542/
方法一：分冶法，递归求解，每次将所求区间折半，一个从中间往左便利，一个从中间向右便利（保证和值存在于连续的区间），即一个左值，一个右值，两者相加求和值，三者比较求最大，不断递归，求最大区间和
suml(1,n)=sum(1,n/2),sumr(1,n)=sum(n/2+1,n);sum=suml+sumr;sum=max(sum,max(suml,sumr));
[1]、a[1:n]的最大子段和与a[1:n/2]的最大子段和相同； 
[2]、a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同；
 [3]、a[1:n]的最大字段和为，且1<=i<=n/2,n/2+1<=j<=n。

可用递归方法求得情形[1],[2]。对于情形[3],可以看出a[n/2]与a[n/2+1]在最优子序列中。因此可以在a[1:n/2]中计算出，并在a[n/2+1:n]中计算出。则s1+s2即为出现情形[3]时的最优值。

代码如下：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <cmath>

#include <map>

#include <set>

#include <vector>

#include <algorithm>

using namespace std;

#define lowbit(x) (x&(-x))

#define max(x,y) (x>y?x:y)

#define min(x,y) (x<y?x:y)

#define MAX 100000000000000000

#define MOD 1000000007

#define PI 3.141592653589793238462

#define INF 0x3f3f3f3f3f

#define mem(a) (memset(a,0,sizeof(a)))

typedef long long ll;

ll a[],n;

ll TDQ(ll *a,ll left,ll right)

{

    if(right==left)

    {

        return a[left]>?a[left]:;

    }

    ll mid=(left+right)>>;

    ll leftsum=TDQ(a,left,mid);

    ll rightsum=TDQ(a,mid+,right);

    ll suml=a[mid],sumr=a[mid+],sl=,sr=;

    ll sum;

    for(ll i=mid;i>=left;i--)

    {

        sl+=a[i];

        suml=max(suml,sl);

    }

    for(ll i=mid+;i<=right;i++)

    {

        sr+=a[i];

        sumr=max(sumr,sr);

    }

    sum=suml+sumr;

    sum=max(sum,max(leftsum,rightsum));

    return sum;

}

int main()

{

    scanf("%lld",&n);

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

        scanf("%lld",&a[i]);

    ll sum=TDQ(a,,n);

    printf("%lld\n",sum);

    return ;

}

方法二：动态规划

区间和b大于0时就往下加，否则归零。

//最大字段求和动态规划

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <cmath>

#include <map>

#include <set>

#include <vector>

#include <algorithm>

using namespace std;

#define lowbit(x) (x&(-x))

#define max(x,y) (x>y?x:y)

#define min(x,y) (x<y?x:y)

#define MAX 100000000000000000

#define MOD 1000000007

#define PI 3.141592653589793238462

#define INF 0x3f3f3f3f3f

#define mem(a) (memset(a,0,sizeof(a)))

typedef long long ll;

ll dp[],a[],n;

int main()

{

    int ans=;

    scanf("%I64d",&n);

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

    {

        scanf("%I64d",&a[i]);

        if(a[i]<) ans++;

    }

    ll sum=,sumson=;

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

    {

        if(sumson>) sumson+=a[i];

        else sumson=a[i];

        sum=max(sum,sumson);

    }

    printf("%I64d\n",sum);

    return ;

}