max sum plus plus(dp).cpp

杭电acm解题报告2001---2099.

#include<cstdio>
#include<memory>
#define Max 1001000
#define max(x,y) ( (x)>(y)? (x):(y))
int m,n,nl[Max],next[Max],pre[Max],tmax;
int main()
{
    int i,j;
    while(scanf("%d %d",&m,&n)==2)
    {
        for(i=1;i<=n;i++)    scanf("%d",&nl[i]) , next[i]=pre[i]=0;
        next[0]=pre[0]=0;
        for(i=1;i<=m;i++)
        {
            tmax=-9999999;
            for(j=i;j<=n;j++)
            {
                next[j]= max( next[j-1] , pre[j-1]) +nl[j];
                pre[j-1]= tmax;
                tmax= max(tmax , next[j]);
            }
            pre[n]=tmax;
        }
        printf("%d\n",tmax);
    }
}