1486【动态规划★★】Max Sum Plus Plus.（求n个数m个不相交子段的最大和）

题目描述

给你一个长度为n的数组（1<=n<=1000000），数组中n个元素S 1, S 2, S 3, S 4 … S n（-32768 ≤ S x ≤ 32767）

我们定义函数sum（i，j） = S i + … + S j (1 ≤ i ≤ j ≤ n)

现在给你一个整数m（0< m<=n）你需要求出 y=sum(i 1, j 1) + sum(i 2, j 2) + sum(i 3, j 3) + … + sum(i m, j m) 的最大值，(i x ≤ i y ≤ j x or i x ≤ j y ≤ j x 是不被允许的）

输入

有多组数据，对于每一组数据，只占一行，输入两个数m和n，然后后面输入n个数S 1, S 2, S 3 … S n

输出

对于每组数据，每组输出占一行，每组输出一个数表示y的最大值

样例输入

1 3 1 2 3

2 6 -1 4 -2 3 -2 3

样例输出

6

8

算法：

dp[i][j]代表前j个元素，i个子段的最大和，第i个子段包含第j个元素，a[j]代表第j个元素值。

所以动态规划方程为：dp[i][j]=MAX{ dp[i][j-1] + a[j] , MAX{ dp[i-1][i~j-1] } + a[j] } 要么把第j个元素加到第i个子段里，要么把第j个元素当作 i子段的第一个元素。

优于m未知，空间复杂程度O(m*n*n)所以，要再优化。

dp[i][j]只与dp[i][j-1]和dp[i-1][i~j-1]有关。所以我们用dp和mmax两个一维数组去存储dp[i]和dp[i-1]。

我们只要保存下dp[i-1,i~j-1]的最大值就不用再去寻找了，因为在寻找第i个子段时，mmax[j-1]用过一次后下次不用了，只有在寻找i+1子段时才用到，所以用过后修改mmax[j-1]，使其存储dp[i~j-1]的最大值，以便下次寻找i+1子段时可以快速取用。

代码实现：

#include <stdio.h>#include <string.h>int a[1000009];int dp[1000009];int mmax[1000009];int max(int a,int b){if(a>b){ return a;}else {return b;}}int main(){int m,n;int max_num;int i,j,k;while(~scanf("%d%d",&m,&n)){memset(dp,0,sizeof(dp));memset(mmax,0,sizeof(mmax));for(i=1;i<=n;i++){scanf("%d",&a[i]);}for(i=1;i<=m;i++){max_num=-10000000;for(j=i;j<=n;j++){dp[j]=max(dp[j-1]+a[j],mmax[j-1]+a[j]);mmax[j-1]=max_num;max_num=max(max_num,dp[j]);}}printf("%d\n",max_num);}return 0;}