/*基礎(chǔ)dpA - Max Sum Plus Plus時間: 2017/02/18題意：在一組數(shù)取出m個不相交的區(qū)間，使區(qū)間和的總和最大。題解：dp[i][j]表示前i個數(shù)，分為j個區(qū)間和的總和最大的值dp[i][j] = max(dp[i-1][j]+a[i], max(dp[0……(i-1)][j-1])+a[i]);因為dp[i][j]只和dp[][j-1]和dp[i-1][j]有關(guān)，所以只需一維數(shù)組即可max(dp[0……(i-1)])可以在i-1層的時候處理出來，優(yōu)化時間。*/#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <queue>#include <vector>#include <map>using namespace std;#define LL long long#define INF 0x3f3f3f3f#define PI acos(-1.0)#define E 2.71828#define MOD 1000000007#define N 1000010#define M 10010const double eps=1e-8;int a[N],dp[N],maxn[N];int main(){    int n,m;    while(~scanf("%d%d",&m,&n))    {        for(int i = 1; i <= n; i++)            scanf("%d",&a[i]);        memset(dp,0,sizeof(dp));        memset(maxn,0,sizeof(maxn));        /*        未優(yōu)化        for(int j = 1; j <= m; j++)        {            for(int i = j; i <= n; i++)            {                dp[i][j] = dp[i-1][j]+a[i];                for(int k = 1; k < i; k++)                    dp[i][j] = max(dp[i][j],dp[k][j]+a[i]);            }        */        int maxnn;        for(int i = 1; i <= m; i++)        {            maxnn = -INF;            for(int j = i; j <= n; j++)            {                dp[j] = max(dp[j-1],maxn[j-1])+a[j];                maxn[j-1] = maxnn;                maxnn = max(maxnn,dp[j]);            }            //PRintf("/n%d/n",maxnn);        }        printf("%d/n",maxnn);    }    return 0;}