网址链接:http://acm.hdu.edu.cn/showproblem.php?pid=1024
给出n个数,求其m个子段和的最大值。
定义:
now[j],表示以第j个元素为结尾的i个子段的最大和,必须包含a[j]。
pre[j],表示前j个元素i个子段的最大和,不一定包含a[j]。
dp[i][j],表示前j个元素i个子段的最大和,包含a[j]
原始状态转移方程:
dp[i][j]=max(dp[i][j-1]+a[j],dp[i-1][k]+a[j]) (i-1<=k<=j-1)
第1种情况是直接将第j个元素加在第i个子段之后,第2种情况是将第j个元素单独作为一个子段,那么前面必须是i-1个子段
解题思路:
这个题目由于n比较大,所以我们开不出dp数组,只有用滚动数组实现上述状态转移方程。
核心代码:
for(i=1;i<=m;i++)
{
Max=-99999999;
for(j=i;j<=n;j++)
{
now[j]=max(now[j-1]+a[j],pre[j-1]+a[j]);
//now[j]有两种来源,一种是直接在第i个子段之后添加a[j]
//一种是是a[j]单独成为1个子段
pre[j-1]=Max; //更新pre使得pre是前j-1个中最大子段和
if(now[j]>Max) Max=now[j];
}
}
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<set> #include<map> #include<vector> #include<algorithm> #define N 1000001 using namespace std; int m,n,Max; //Max保存这最大值 int now[N]; //包含第j个数据的最大和 int pre[N]; //前j个数据的最大和 int a[N]; int main() { //freopen("in.txt","r",stdin); int i,j; while(scanf("%d%d",&m,&n)==2) { for(i=1;i<=n;i++) scanf("%d",&a[i]); memset(now,0,sizeof(now)); memset(pre,0,sizeof(pre)); for(i=1;i<=m;i++) { Max=-99999999; for(j=i;j<=n;j++) { now[j]=max(now[j-1]+a[j],pre[j-1]+a[j]); //now[j]有两种来源,一种是直接在第i个子段之后添加a[j] //一种是是a[j]单独成为1个子段 pre[j-1]=Max; //更新pre使得pre是前j-1个中最大子段和 if(now[j]>Max) Max=now[j]; } } printf("%d\n",Max); } return 0; }