A - Max Sum Plus Plus

题目入口：A - Max Sum Plus Plus
杭电入口：Max Sum Plus Plus

解题思路

题意：给定分组个数 给定一串数字 在规定分组个数下 求各组之和的总和的最大值
思路：a[]存放原始数据
dp[j-1]存放前j-1个数分成i个组得到的最大总和 j不单独成组(并入到j-1个数分好i组后的最后一组)
Max[j-1]存放1～j-1个数分成i-1组取得的最大总和 j单独成组
dp[j]存放分到第j个数(严格讲是遍历到 因为前面的数可以选择不加入分组中 且第i个数也可以选择不加入到分组中)分组和的最大值
所以这里dp[j]选择dp[j-1](j不单独成组)以及Max[j-1]+a[i](j单独成组)两种情况的更大值
那么Max[]是怎么实现存放1～j-1个数分成i-1组取得的最大总和的呢
这里我们采用mmax来记录第j次分组策略的最大值 并将其赋值给Max[]
那么来到第j+1次分组时 我们使用的Max[]的值便是上一组策略的最大值
这样理解了以后把j与j+1往前推一下变成j-1和j就迎刃而解了
最终mmax的值便是最终的答案
到这里讲解结束

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define inf 0x3f3f3f3f
using namespace std;
const int MaxSize = 1e6+10;
int a[MaxSize];     //存放源数组
int dp[MaxSize];    //dp[j-1]存放前j-1个数分成i个组得到的最大总和 j不单独成组
int Max[MaxSize];   //Max[j-1]存放1～j-1个数分成i-1组取得的最大总和 j单独成组
int main() {
    int n, m, mmax = -inf;
    while (~scanf("%d%d", &m, &n)){
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);    //获得源数组
        memset(dp, 0, sizeof(dp));
        memset(Max, 0, sizeof(Max));
        for (int i = 1; i <= m; i++){   //分成i个组
            mmax = -inf;    //开始新的组数分配时初始化无穷小
            for (int j = i; j <= n; j++){   //当前数字个数
                dp[j] = max(dp[j-1], Max[j-1]) + a[j];
                //比较两种情况(第j个数是否单独成组) 取最大值
                Max[j-1] = mmax;
                mmax = max(mmax, dp[j]);
            }
        }
        printf("%d\n", mmax);   //输出得到的最大总和
    }
    return 0;
}