经典的DP题 状态方程 d[i][j]=max{d[i][j-1],d[i-1][t]} i<t<jn很大，这样的数组开不了！ d[i][j]的值只用到d[i][j-1],d[i-1][j] 所以用两个一维数组表示 b[],c[] 解决上式用了三重循环。铁定超时。 所以第二重循环中用c［］记录max{d[i-1][t]},i<t<j;  这样时间复杂度就降低了 程序： #include<stdio.h>#include<string.h>#include<malloc.h>//#include<limits.h>#define MAX1 1000000long a[MAX1];long b[MAX1];long c[MAX1];int main(){    long i,j,m,n;    long max,sum;    while(scanf("%d %d",&m,&n)!=EOF)    {        memset(b,0,(n+1)*sizeof(b[0]));        memset(c,0,(n+1)*sizeof(c[0]));        for(i=1;i<=n;i++)            scanf("%ld",&a[i]);        b[0]=c[1]=0;                for(i=1;i<=m;i++)        {            b[i]=b[i-1]+a[i];            c[i-1]=b[i];            max=b[i];            for(j=i+1;j<=n-m+i;j++)            {                b[j]=b[j-1]>c[j-1]?b[j-1]+a[j]:c[j-1]+a[j];                c[j-1]=max;                if(max<b[j]) max=b[j];            }            c[i+n-m]=max;        }         sum=INT_MIN;        for(j=m;j<=n;j++)            if(sum<b[j]) sum=b[j];        printf("%ld\n",sum);    }    return 0;}

评论