题目链接：Max Sum Plus Plus Plus
AC代码及注释
本题是最大m段连续子串和问题的加大版，m段的每段的数字个数是变换的，不过同样的，也可以使用动态规划算法进行求解。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n, m;
//a用于装n个数，b用于装m段的不同数，sum是a的累加和，sum的设置方便计算
int a[1001], b[1001], sum[1001];
//动态规划表，dp[i][j]为i个元素分为j段的最大和
int dp[1001][1001];
int main()
{
int i, j;
while(scanf("%d", &n) && n){
//每次进入首先对dp数组清零
memset(dp, 0, sizeof(dp));
//数字序列a的累加和第一个赋值为0，下标是从1开始的，所以此处赋值0
sum[0] = 0;
//输入段的数目
scanf("%d", &m);
//输入每段的数字个数
for(i = 1; i <= m; i++)
scanf("%d", &b[i]);
//输入数字，并计算每个下标下的累加和
for(i = 1; i <= n; i++){
scanf("%d", &a[i]);
sum[i] = sum[i-1] + a[i];
}
//动态规划表的计算
for(i = 1; i <= n; i++){//对n个数字的遍历
for(j = 1; j <= m; j++){//第j段，一共m段
//i>=b[j]表示数字个数多余段数，比如10个数字分为8段，此时的选择有两种
//(1)i个数字分为j段的最大和由i-1个数字分为j段得来，如第i个为负数情况，不加它的和更大
//(2)由i-b[j]个数字分为j-1段，加上b[j]个数字作为1段，共j段组成
//在(2)中，b[j]个数字的和即为当前i下的累加和sum[i]减去前i-b[j]个数字的累加和
if(i >= b[j])
dp[i][j] = max(dp[i-1][j], dp[i-b[j]][j-1]+sum[i]-sum[i-b[j]]);
//如果i<b[j],比如3个数分为五段，则直接选用i-1个数字分为j段的结果
else
dp[i][j] = dp[i-1][j];
}
}
printf("%d\n", dp[n][m]);
}
return 0;
}
