『算法-ACM 竞赛-最大字段和』51NOD1049 最大子段和动态规划模板板子 DP

51 NOD 1049 最大子段和 动态规划 模板 板子 DP

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。

收起

输入

第1行：整数序列的长度N（2 <= N <= 50000)
第2 - N + 1行：N个整数（-10^9 <= A[i] <= 10^9）

输出

输出最大子段和。

输入样例

6
-2
11
-4
13
-5
-2

输出样例

20



#include<iostream>
#include<queue>
#include<algorithm>
#include<set>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<bitset>
#include<cstdio>
#include<cstring>
//---------------------------------Sexy operation--------------------------//

#define cini(n) scanf("%d",&n)
#define cinl(n) scanf("%lld",&n)
#define cinc(n) scanf("%c",&n)
#define cins(s) scanf("%s",s)
#define coui(n) printf("%d",n)
#define couc(n) printf("%c",n)
#define coul(n) printf("%lld",n)
#define speed ios_base::sync_with_stdio(0)
#define file  freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
//-------------------------------Actual option------------------------------//

#define Swap(a,b) a^=b^=a^=b
#define Max(a,b) a>b?a:b
#define Min(a,b) a<b?a:b
#define mem(n,x) memset(n,x,sizeof(n))
#define mp(a,b) make_pair(a,b)
//--------------------------------constant----------------------------------//

#define INF  0x3f3f3f3f
#define maxn  100005
#define esp  1e-9
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
//------------------------------Dividing Line--------------------------------//
ll a[maxn];
ll ans[maxn];
ll ANS=0;
int  main()
{
    int m;
    cin>>m;
    for(int i=1; i<=m; i++)
    {
        cinl(a[i]);
        ans[i]=max(ans[i-1]+a[i],a[i]);
        ANS=max(ANS,ans[i]);
    }
    cout<<ANS<<endl;
}