给定一个长度为n的区间：求m段连续子区间的和 最大值（其中m段子区间互不相交）
思路： dp[i][j]: 前j个元素i个连续区间最大值 （重要 a[j]必须在最后一个区间内）
转移方程：dp[i][j]=max (dp[i][j-1],dp[i-1][t]) + a[j] ( dp[i-1][t] 是 max ( dp[i-1[k] 1<=k<=j-1 )
第j个元素与第j-1个元素连在一起 ---》dp[i][j-1]
第j个元素单独一个区间 ----》dp[i-1][t]
重要： 1）如何优化
2）遍历推导的顺序 （想想为什么是 i在前 ，j在后）
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e6+;
const int INF=0x3f3f3f3f;
int a[N],dp[N],pre[N];
int n,m;
int main ()
{
while (~scanf ("%d %d",&m,&n)) {
memset (dp,,sizeof(dp));
memset (pre,,sizeof(pre));
for (int i=;i<=n;i++)
scanf ("%d",&a[i]);
for (int i=;i<=m;i++) {
int _max=-INF;
for (int j=i;j<=n;j++) {
dp[j]=max (dp[j-],pre[j-])+a[j]; // dp[j] 前j个元素i段最大值
pre[j-]=_max; // pre[j] 1~j 之中最大 dp[i-1][t]
_max=max (_max,dp[j]);
}
}
int ans=dp[m];
for (int i=m;i<=n;i++) // !!因为从i=1开始而导致的错误
ans=max (dp[i],ans);
printf ("%d\n",ans); // !!可以直接 printf ("%d\n",_max); }
return ;
}