算法笔记――最大子段和问题，最大子矩阵和问题，最大m子段和问题(二)
>s2)
{
s2=rights;
}
}
sum = s1+s2;
if(sum
{
sum = leftsum;
}
if(sum
{
sum = rightsum;
}
}
return sum;
}
int MaxSum(int n,int *a)
{
return MaxSubSum(a,0,n-1);
}
算法所需的计算时间T(n)满足一下递归式：
解此递归方程可知：T(n)=O(nlogn)。
(3)动态规划算法求解
算法思路如下：
记，则所求的最大子段和为：
由b[j]的定义知，当b[j-1]>0时，b[j]=b[j-1]+a[j]，否则b[j]=a[j]。由此可得b[j]的动态规划递推式如下：
b[j]=max{b[j-1]+a[j],a[j]},1<=j<=n。
具体代码如下：
[cpp]
//3d4-1 最大子段和问题的动态规划算法
#include "stdafx.h"
#include
using namespace std;
int MaxSum(int n,int *a);
int main()
{
int a[] = {-2,11,-4,13,-5,-2};
for(int i=0; i<6; i++)
{
cout<
}
cout<
cout<<"数组a的最大连续子段和为:"<
容易看出，这正是一维情形的最大子段和问题。因此，借助最大子段和问题的动态规划算法MaxSum，可设计出最大子矩阵和动态规划算法如下:
int MaxSum(int n,int *a);
return 0;
}
int MaxSum(int n,int *a)
{
int sum=0,b=0;
for(int i=1; i<=n; i++)
{
if(b>0)
{
b+=a[i];
}
else
{
b=a[i];
}
if(b>sum)
{
sum = b;
}
}
return sum;
}
上述算法的时间复杂度和空间复杂度均为O(n)。
2、最大子矩阵和问题
(1)问题描述：给定一个m行n列的整数矩阵A，试求A的一个子矩阵，时期各元素之和为最大。
(2)问题分析：
用二维数组a[1:m][1:n]表示给定的m行n列的整数矩阵。子数组a[i1:i2][j1:j2]表示左上角和右下角行列坐标分别为(i1,j1)和(i2,j2)的子矩阵，其各元素之和记为：
最大子矩阵问题的最优值为。如果用直接枚举的方法解最大子矩阵和问题，需要O(m^2n^2)时间。注意到，式中，，设，则
容易看出，这正是一维情形的最大子段和问题。因此，借助最大子段和问题的动态规划算法MaxSum，可设计出最大子矩阵和动态规划算法如下:
[cpp]
//3d4-5 最大子矩阵之和问题
#include "stdafx.h"
#include
using namespace std;
const int M=4;
const int N=3;
int MaxSum2(int m,int n,int a[M][N]);
int main()
{
int a[][N] = {{4,-2,9},{-1,3,8},{-6,7,6},{0,9,-5}};
for(int i=0; i
{
for(int j=0; j
{
cout<
}
cout<
}
cout<
cout<<"数组a的最大连续子段和为:"<
return 0;
}
int MaxSum2(int m,int n,int a[M][N])
{
int sum = 0;
int *b = new int[n+1];
for(int i=0; i
{
for(int k=0; k
{
b[k]=0;
}
for(int j=i;j
{
for(int k=0; k
{
b[k] += a[j][k];//b[k]为纵向列之和
int max = MaxSum(n,b);
if(max>sum)
{
sum = max;
}
}
}
}
return sum;
}
int MaxSum(int n,int *a)
{
int sum=0,b=0;
for(int i=1; i<=n; i++)
{
if(b>0)
{
b+=a[i];
}
else
{
b=a[i];
}
if(b>sum)
{
sum = b;
}
}
return sum;
}
以上代码MaxSum2方法的执行过程可用下图表示：
3、最大m子段和问题
(1)问题描述：给定由n个整数(可能为负数)组成的序列a1,a2,a3……an,以及一个正整数m,要求确定此序列的m个不相交子段的总和达到最大。最大子段和问题是最大m字段和问题当m=1时的特殊情形。
(2)问题分析：设b(i,j)表示数组a的前j项中i个子段和的最大值，且第i个子段含a[j](1<=i<=m,i<=j<=n),则所求的最优值显然为。与最大子段问题相似，计算b(i,j)的递归式为：
其中，表示第i个子段含a[j-1],而项表示第i个子段仅含a[j]。初始时，b(0,j)=0,(1<=j<=n);b(i,0)=0,(1<=i<=m)。
具体代码如下：
[cpp]
//3d4-6 最大m子段问题
#include "stdafx.h"
#include
using namespace std;
int MaxSum(int m,int n,int *a);
int main()
{
int a[] = {0,2,3,-7,6,4,-5};//数组脚标从1开始
for(int i=1; i<=6; i++)
{