【书上讲解】最大m段子段和问题

描述

【题解】

设f[i][j]表示前i个数字分成了j段的最大子段和。
则f[i][j] = max(f[i-1][j]+a[i] (第i个数字和第j段合在一起),f[k][j-1]+a[i] (第i个数字作为第j段的第一个数字,同时在j-1段的情况中找到和最大的那个))
这样的时间复杂度是$O(m*n^2)$的,代码的写法在代码1中
接下来我们做一些优化。
首先把数组的第二维改成滚动数组。
然后令F[i][j]=max(f[1..i][j]);
这样在做第二层的转移的时候f[i][j]就能直接用F[i-1][j-1]做转移了
当然也不用非得再重开一个新的数组。
在f[i][j]做完转移之后把它改成前缀的最大值就行。(注意一定要做完转移之后再改变,因为f[i][j]在转移的时候用到了f[i-1][j])
这样在做转移的时候就少掉了O(N)的一次枚举了
复杂度变成O(n*m)的了.详见代码2

【代码1】

#include <cstdio>

#include <algorithm>

using namespace std;

const int N = 1e6;

const int M = 30;

int f[N+10][M+10],a[N+10];

int n,m;

int main(){

    while (~scanf("%d%d",&m,&n)){

        for (int i = 1;i <=n;i++) scanf("%d",&a[i]);

        for(int l = 1;l <= m;l++){

            for (int i = l;i <= n;i++){

                if (i==l){

                    f[i][l] = f[i-1][l-1]+a[i];

                }else{

                    f[i][l] = f[i-1][l]+a[i];//和第l段合并

                    //printf("%d ",f[i][l]);

                    //自己独立成段

                    for (int k = l-1;k <= i-1;k++)

                        f[i][l] = max(f[i][l],f[k][l-1]+a[i]);

                }

            }

        }

        int ans = f[m][m];

        for (int i = m+1;i <= n;i++) ans = max(ans,f[i][m]);

        printf("%d\n",ans);

    }

    return 0;

}

【代码2】

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N = 1e6;

const int M = 30;

int f[N+10][2],a[N+10];

int n,m;

int main(){

    while (~scanf("%d%d",&m,&n)){

        for (int i = 1;i <=n;i++) scanf("%d",&a[i]);

        memset(f,0,sizeof f);

        for(int l = 1;l <= m;l++){

            for (int i = l;i <= n;i++){

                if (i==l){

                    f[i][l&1] = f[i-1][(l-1)&1]+a[i];

                }else{

                    f[i][l&1] = f[i-1][l&1]+a[i];//和第l段合并

                    //printf("%d ",f[i][l]);

                    //自己独立成段

                    f[i][l&1] = max(f[i][l&1],f[i-1][(l-1)&1]+a[i]);

                }

            }

            for (int i = l+1;i <= n;i++)

                f[i][l&1] = max(f[i][l&1],f[i-1][l&1]);

        }

        printf("%d\n",f[n][m&1]);

    }

    return 0;

}