最大字段和的扩展—最大子矩阵和及最大m字段和问题

关于最大字段和，已有4中方法对其进行求解，现对其进行扩展，得到两个扩展的问题：

一、最大子矩阵问题

1、问题描述：给定一个m行n列的子矩阵A，试求出矩阵A的一个子矩阵，使其各元素之和为最大。

2、求解策略：对该问题，如果用穷举法求解，时间复杂度将为O(m2n2)，利用其为最大字段和问题的扩展，将其划归成最大字段和问题，然后再用最大字段和的最优方法进行求解，则可降低时间复杂到O(m2n) 。即先长度为m的维度上求出第i行到第j行每一个的元素和存储到一个n维的数组中，再对该数组进行最大字段和的动态规划法求解，求出结果。

3、程序如下所示：

 

复制代码
float maxSum2(float (*a)[4], int row, int col)
{
int i = 0, j = 0, k = 0;
float maxs = 0, maxSoFar = 0, maxendinghere = 0, * b = new float[col];
for (i = 0; i < row; ++i)
{
for (k = 0; k < col; ++k)
b[k] = 0;
for (j = i; j < row; ++ j)
{
for (k = 0; k < col; ++k)
b[k] += a[j][k]; //b[k]存储的是第i行到第j行每列的元素和

//动态规划法求解b中的最大子和
maxendinghere = 0;
maxSoFar = 0;
for (k = 0; k < col; ++k)
{
maxendinghere = maxendinghere + b[k];
maxendinghere = maxendinghere > 0 ? maxendinghere : 0;
maxSoFar = maxSoFar < maxendinghere ? maxendinghere : maxSoFar;
}

maxs = maxs < maxSoFar ? maxSoFar : maxs;
}
}
delete b;
return maxs;
}
复制代码
二、最大m字段和问题

1、问题描述：给定n个数（可能是负数）组成的序列a1,a2,…,an以及一个正整数m，要去确定该序列m个互不相交字段，使这m个字段的总和达到最大。

2、求解策略：显然最大m字段和问题是最大字段和问题在字段个数上的推广。同样可以考虑用动态规划方法求解。设b(i,j)表示数组a的前j项中i个字段和的最大值，且第i个字段含a[j]，则所求的最优值为max b(m,j)(m≤j≤n)。该动态规划的转移方程则为：

b(i,j) = max{b(i,j-1)+a[j],max b(i-1,t)+a[j]},(i-1≤t<j,1≤i≤j≤m,1≤j≤n,)

且初始时，b(0,j)=0,b(i,0)=0.

3、根据2得到的动态规划，对于源程序设计，记住并不是所有的表b[m+1][n+1]都要求的，由i≤j可知下三角部分不需要计算，且对角线上的元素为所有i个元素的和。又根据b的最后一行只有b(m,j)共n-m+1个元素，且根据b(i,j)的计算公式中的第二项知道其只要b(m-1,j)共n-m+1个，依次类推知道每行都只要计算j=i~j=i+n-m个元素。源程序如下：

复制代码
float maxMSum(float* a, int m, int n)
//求含有n个元素的序列a的最大m字段和
{
int i = 0, j = 0, k = 0;
float sum = 0;
if (n < m || m < 1)
return 0;

//因为初值b[i][0]和b[0][j]，所以数组大小为(m+1)*(n+1)
float** b = new float* [m+1];//声明b为指向指针数组的指针（指针的指针）
for (i = 0; i <= m; ++i)
b[i] = new float[n+1]; //b[i]指向的是一个n+1维大小的数组

//赋初值
for (i = 0; i <= m; ++i)
b[i][0] = 0;
for (j = 1; j <= n; ++j)
b[0][j] = 0;

//根据转移方程依次求出b[i][j]
for (i = 1; i <= m; ++i)
for (j = i; j <= n-m+i; ++j)
//n-m+i避免多余的运算，当i=m时，j最大为n，最小为m，而依照递归公式
//其只要求出b[m-1][m-1],…,b[m-1][n-1]共n-m个元素,依次类推
{
if (j > i)//元素个数大于字段个数
{
b[i][j] = b[i][j-1] + a[j-1]; //第i个字段含a[j-1]的情况，这里及以下a都不是a[j]而是a[j-1]因为a从0开始
for (k = i-1; k < j; ++k); //第i个字段仅含a[j]
if (b[i][j] < b[i-1][k]+a[j-1])
b[i][j] = b[i-1][k]+a[j-1];
}
else//元素个数等于字段个数，字段和即为序列的和
b[i][j] = b[i-1][j-1]+a[j-1];
}

//扫描b[m][j]（m<=j<=n)求出最大值
for (j = m; j < n; ++j)
if (sum < b[m][j])
sum = b[m][j];

for (i= 0; i<= m; ++i){
for (j = 0; j <= n; ++j)
cout << b[i][j] << ‘ ‘;
cout << endl;
}
delete [] b;
return sum;
}
复制代码
4、上述方法的改进，显然，上述方法的时间复杂度为O(mn2)，空间复杂度为O(mn)。注意到每次计算b(i,j)时只利用了本行i和上一行的一个最大值进行求解，故算法中只要存储数组b的当前行以及上一行的最大值max (i-1,t)(i-1≤t<j)即可。故只要两个数组的额外空间b[n+1],c[n+1],且c(i)=max b(i,t) (i≤t<j),b(i,j)=max(b(i,j-1),c(i-1)) + a[j].此时的时间复杂度为O(m(n-m))，空间复杂度为O(n).

5、改进后的源程序和测试程序如下：

复制代码
float maxMSumImp(float* a, int m, int n)
{
if (n < m || m < 1)
return 0;
int i = 0, j = 0;
float sum = 0, maxb = 0;
float* b = new float[n+1],//对i个字段和都只存储n-m+1个有用的值，虽然大小为n+1
* c = new float[n+1];//额外数组，c[i][j]=max b(i,t)(i <= t < j)的值，开始应该都赋值为-inf
b[0] = 0;
c[1] = 0;
for (i = 1; i <= m; ++i) //依次求出i个子段时的情况
{
b[i] = b[i-1] + a[i-1];//i个元素的i子段和为其序列的全部和,其实为b[i][i]=…
maxb = b[i]; //其实为maxb=max b(i,t) (i <= t < j=i+1)，此时只存储了一个有效值(i个字段时）
//cout << b[i] << ‘ ‘;
for (j = i+1; j <= n-m+i; ++j) //一个这样的循环对应着i个字段时求相应的值
{
cout << c[j-1] << ‘ ‘;
b[j] = (b[j-1] > c[j-1] ? b[j-1] : c[j-1])+a[j-1];//这里的a[j-1]同样是因为a从0开始
c[j-1] = maxb; //其实为c[i][j-1],为第i+1子段做准备
if (maxb < b[j])
maxb = b[j];

}
c[n-m+i] = maxb;
cout << endl;
}
for (j = m; j <= n; ++j)
if (sum < b[j])
sum = b[j];
delete[] b;
delete[] c;
return sum;
}
复制代码
测试程序：

 

复制代码
int main()
{
int a[] = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84},
n, besti = 0, bestj = 0, maxSum = 0;
float b[3][4] = {31, -41, 59, 26,
-1, 16, -27, 18,
64, -28, 36, -19};
float c[] = {-1, 3, -1, 4, -2, -3, 5, -2, 3, -1};
int m = 2,n3;
n3 = sizeof(c)/sizeof(c[0]);
cout << “序列C的最大 ” << m << ” 字段和为：” << maxMSumImp(c,m,n3) << endl;
return 0;
}
复制代码