51Nod 1049最大子段和 | 模板

Input示例

6

-2

11

-4

13

-5

-2

Output示例

20

1.最大子段和模板

#include "bits/stdc++.h"

using namespace std;

#define rep(i, s, n) for(int i=s;i<n;i++)

#define LL long long

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

#define E 2.71828

#define MOD 1000000007

#define N 50010

LL a[N];

LL b[N];

int main()

{

    LL max1 = ;

    int n;

    while(~scanf("%d",&n))

    {

        bool f=;

        rep(i,,n){

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

        }

        memset(b,,n+);

        max1=-INF;

        rep(i,,n)

        {

           if(b[i-]>)

           {

             b[i] = b[i-]+a[i];

           }else{

             b[i] = a[i];

           }

           if(b[i]>max1)

             max1 = b[i];

        }

        if(max1<)

            max1=;

        cout<<max1<<endl;

    }

    return ;

}

2.

预处理：前缀和
last：上一个正数的位置
dp[i]表示这个子段最后一个是i的最大和
状态转移：
如果前一个是非负数，dp[i]=dp[i-1]+a[i]
否则，dp[i]=max(a[i],dp[last]+sum[i]-dp[last])
原理跟最大字段和一样

#include "bits/stdc++.h"

using namespace std;

#define rep(i, s, n) for(int i=s;i<n;i++)

#define LL long long

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

#define E 2.71828

#define MOD 1000000007

#define N 50010

int n;

long long a[N],dp[N],sum[N];

int main()

{

    while(~scanf("%d",&n)){

        int last=;

        rep(i,,n+) cin>>a[i];

        rep(i,,n+) sum[i]=sum[i-]+a[i];

        rep(i,,n+)

        {

            if(a[i-]>=)

                dp[i]=dp[i-]+a[i],last=i;

            else

                dp[i]=max(a[i],dp[last]+sum[i]-sum[last]);

        }

        LL ans=;

        rep(i,,n+)

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

        printf("%lld",ans);

    }

    return ;

}