最大m段子段和

hdu1024 最大m子序列和

给定你一个序列，让你求取m个子段（不想交的子段）并求取这m个子段和的最大值

从二维开始来看dp[i][j]表示取第j个数作为第i个子段的元素所得到的前i个子段和的最大值，那么第j个元素必取

1.第j个元素是第i个子段的开头——dp[i][j] = max(dp[i-1][k]) + a[j] k = [1,j-1] ——最大值肯定是前i-1个子段的最大值加上当前的a[j]

2.第j个元素是第i个子段的中间——dp[i][j] = dp[i-1][j] + num[j]

所以看看1和2谁大就好

但是数据m——子段的个数么有范围限制，也就是我们必须要优化到维度，也就是去掉i这个维度

dp[j] = max(dp[j-1],max_array[j-1]) + a[j]，所以我们要记录前j-1个数的最大子段和，然后层层更新优化

由此可见dp[j]就是包括第j个元素的前i个子段的最大和

那么max_array[]数组呢，就是不包括j（所以索引为j-1）的前i-1个最大元素子段和

有些疑惑，哎，为什么更新的时候更新的事max_array【j-1】啊，上面都用到了他了，下面才更新

在注意理解一下，当前用到的max_array数组是i-1存储的，所以当i++后我们又为后续的铺垫好了

#include <iostream>
#include <cstdio>
#include <string.h>
#include <cmath>
#define inf 0xffffff
using namespace std;
const int maxn = 1e6 + 1e3;
int dp[maxn];
int a[maxn];
int max_array[maxn];
int main()
{
    int m,n;
    while(~scanf("%d%d",&m,&n))
    {
        for(int i = 1;i <= n;i++)
        {
            scanf("%d",&a[i]);
        }
        memset(dp,0,sizeof(dp));
        memset(max_array,0,sizeof(max_array));
        int res;
        for(int i = 1;i <= m;i++)
        {
            res = -inf;
            for(int j = i;j <= n;j++)
            {
                if(i == j)dp[j] = max_array[j-1] + a[j];
                else dp[j] = max(dp[j-1],max_array[j-1]) + a[j];

                max_array[j-1] = res;
                if(res < dp[j])res = dp[j];
            }
        }

        printf("%d
",res);
    }
    return 0;
}