A - Max Sum Plus Plus DP题解

看别人题解写出来的，指路:https://blog.51cto.com/13688928/2117013
题目意思：在一个数列里找m个字段，使得他们的和最大。
dp[i][j]来表示在前j个数中，以下标j结尾并分为i段的最大和。
动态转移方程：dp[i][j]=max(dp[i][j-1]+a[j],max(dp[i-1][k]) + a[j] ) (0<k<j)
下面解释k的意义：
max( dp[i-1][k] ) + a[j] )表示的前k个数分成i-1组时的最大值。
所以也要对k进行遍历来求解max（dp[i-1][k]),但这样显然会超时。所以可以用一个pre【】数组来记录前j个分为i组的最大值。

#include <iostream>
#include<stdio.h>
#include <cstring>
#include <algorithm>
#include <string.h>
#include <queue>
//#include <bits/stdc++.h>
#define pb push_back
#define qc std::ios::sync_with_stdio(0);
using namespace std;
const int max_n=1000005;
typedef long long ll;
typedef unsigned long long int ul;
typedef double dl;
int a[max_n],pre[max_n];
int dp[max_n];
int main()
{
    int n,m,maxn;
    while(~scanf("%d %d",&m,&n))
    {
        for(int i=1;i<=n;i++)    
    scanf("%d",&a[i]);

        memset(dp,0,sizeof(dp));
        memset(pre,0,sizeof(pre));
        for(int i=1;i<=m;i++)
        {
            maxn=-1000000;
            for(int j=i;j<=n;j++)
            {
                dp[j]=max(pre[j-1],dp[j-1])+a[j];
                pre[j-1]=maxn;
                maxn=max(maxn,dp[j]);
            }
        }
        printf("%d\n",maxn);
    }
}