思路：
dp[i][j]表示前j个元素分成i段的最优解.
转移方程:dp[i][j]=max{dp[i][j-1]+a[j]，max(dp[i-1][j-1]+a[j],dp[i-1][j-2])}
每一个i其中j的上下界的确定,现在分别解释上界和下界：
上界：dp[i][j]中，如果j=i-1，意思就是在前面i-1个元素中分成i段，这个是不可能实现的,所以上界为i；
下界：n-m+i;
（这也是一种优化，因为对于每一个i，只要确定在j的范围(i<=j<=n-m+i)内的dp[i][j]）
这是其中一个特例的状态转移表 m=4，n=6 ，-1 4 -2 3 -2 3
图示：转移方程演示：
最后结果呈现：
没填的不用算。
很显然dp[i][i]=dp[i-1][i-1]+a[i],
所以对角线上面有：
现在演示一下转移过程。如何求下图的框中的元素的值
由下面涂色的元素的最大值加上a[3]=-2求的如下图
最大的是4，所以4+（-2）=2；框中填2;
AC代码如下：
#include<stdio.h>
#include<string.h>
#define N 1000001
#define inf 0x3f3f3f3f
int dp[2][N],num[N]; /*dp[2][N]表示滚动数组，可以在d[0][N]与dp[1][N]之间交替切换，分别表示当前值和原先值*/
int Max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int m,n;
int i,j,flag,sum;
while(scanf("%d%d",&m,&n)!=-1)
{
for(i=1;i<=n;i++)
{
scanf("%d",&num[i]);
dp[0][i]=dp[1][i]=0; /*初始化都为0*/
}
flag=1; /*标记flag，可以使dp[flag][N]在d[0][N]与dp[1][N]之间交替切换*/
for(i=1;i<=m;i++)
{
dp[flag][i]=dp[!flag][i-1]+num[i];
dp[!flag][i]=Max(dp[!flag][i],dp[!flag][i-1]);
for(j=i+1;j<=n-m+i;j++)
{
dp[flag][j]=Max(dp[flag][j-1],dp[!flag][j-1])+num[j];
dp[!flag][j]=Max(dp[!flag][j],dp[!flag][j-1]);
}
flag=!flag; /*切换，把当前值变为原先值*/
}
flag=!flag;
sum=-inf;
for(i=m;i<=n;i++)
{
if(dp[flag][i]>sum)
sum=dp[flag][i];
}
printf("%d\n",sum);
}
return 0;
}