参考了一下 http://moxi466839201.blog.163.com/blog/static/18003841620110220374942/

滚动数组   状态转移方程不太好理解 ....  f[i][j]=max(f[i][j-1],f[i-1][j-1])+a[j];

#include<cstdio>

#include<cstring>

#include<iostream>

#define maxn 1000010

#define INF 1000000000

using namespace std;

int dp[maxn],pre[maxn],a[maxn];

int main()

{

    int n,m,_max;

    while(scanf("%d%d",&m,&n) == 2)

    {

        memset(dp, 0, sizeof(dp));

        memset(pre, 0, sizeof(pre));

        for(int i = 1; i <= n; i++) scanf("%d",&a[i]);

        for(int i = 1; i <= m; i++)

        {

            _max = -INF;

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

            {

                dp[j] = max(dp[j-1], pre[j-1])+a[j];

                pre[j-1] = _max;

                _max = max(_max, dp[j]);

            }

        }

        printf("%d\n",_max);

    }

    return 0;

}