本文主要是介绍动态规划2：最大子段和问题到最大子矩阵问题（二）：最大n子段和问题详谈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述：最长n子段和问题
有了最大子段和问题的基础，将一维数据变成二维数据
dp[i][j]保存前j个元素（包括j）分成i段最长连续子序列和
则有dp[i][j]=max(dp[i][j-1]+num[j],max(dp[i-1][t]+num[j])) i-1<=t<j
注意t的取值范围，所以不经过优化的代码如下：
int DP(int a[],int m,int n)
{ int dp[100][100];memset(dp,0,sizeof(dp));int maxL,maxV=INT_MIN;for(int i=1;i<=m;i++){for(int j=i;j<=n;j++){maxL=INT_MIN;for(int t=i-1;t<j;t++){maxL=max(maxL,dp[i-1][t]);}dp[i][j]=max(dp[i][j-1],maxL)+a[j];}}for(int i=1;i<=n;i++)maxV=max(maxV,dp[m][i]);return maxV;
} 可以看到这个算法时间复杂度为O(n^3)，空间复杂度为O(m*n)，大数据范围时间和空间都不能满足
我们先对时间复杂度进行优化，注意到t每次都是从i-1到j-1位置遍历，重复工作做得太多，我们可以利用一数组pre[t]来保存从i-1位置到t位置的dp[i-1][t]最大值，供dp[i][j]来使用，使用完之后再将pre[t]赋值成从i位置到dp[i][t]位置的最大值，供后来的i+1使用，注意pre赋值的先后顺序
int DP(int a[],int m,int n)
{ int dp[100][100];int pre[100];memset(dp,0,sizeof(dp));memset(pre,0,sizeof(pre));int maxL,maxV=INT_MIN;for(int i=1;i<=m;i++){maxL=INT_MIN;for(int j=i;j<=n;j++){dp[i][j]=max(dp[i][j-1],pre[j-1])+a[j];pre[j-1]=maxL;maxL=max(maxL,dp[i][j]);}}for(int i=1;i<=n;i++)maxV=max(maxV,dp[m][i]);return maxV;
} 从上面代码中可看出时间复杂度降为了O(n^2)
然后我们再对空间进行优化，这个规律就比较明显了
从这行代码可以看出
dp[i][j]=max(dp[i][j-1],pre[j-1])+a[j];而且还注意到到i=m时，最后从for'循环出来的maxL值就是dp[m][t]的最大值，所以最后一行求maxV的代码就可以省了
最后精简的代码如下，（申请的空间是随意的，可以根据适时情况做出调整）
int DP(int a[],int m,int n)
{ int dp[100];int pre[100];memset(dp,0,sizeof(dp));memset(pre,0,sizeof(pre));int maxL;for(int i=1;i<=m;i++){maxL=INT_MIN;for(int j=i;j<=n;j++){dp[j]=max(dp[j-1],pre[j-1])+a[j];pre[j-1]=maxL;maxL=max(maxL,dp[j]);}}return maxL;
}
这篇关于动态规划2：最大子段和问题到最大子矩阵问题（二）：最大n子段和问题详谈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
