算法笔记――最大子段和问题，最大子矩阵和问题，最大m子段和问题(三)
(int m,int n,int *a)
{
if(n
return 0;
int **b = new int *[m+1];
for(int i=0; i<=m; i++)
{
b[i] = new int[n+1];
}
for(int i=0; i<=m; i++)
{
b[i][0] = 0;
}
for(int j=1;j<=n; j++)
{
b[0][j] = 0;
}
//枚举子段数目，从1开始，迭代到m，递推出b[i][j]的值
for(int i=1; i<=m; i++)
{
//n-m+i限制避免多余运算，当i=m时，j最大为n，可据此递推所有情形
for(int j=i; j<=n-m+i; j++)
{
if(j>i)
{
b[i][j] = b[i][j-1] + a[j];//代表a[j]同a[j-1]一起，都在最后一子段中
for(int k=i-1; k
{
if(b[i][j]
b[i][j] = b[i-1][k]+a[j];//代表最后一子段仅包含a[j]
}
}
else
{
b[i][j] = b[i-1][j-1]+a[j];//当i=j时，每一项为一子段
}
}
}
int sum = 0;
for(int j=m; j<=n; j++)
{
if(sum
{
sum = b[m][j];
}
}
return sum;
}
上述算法的时间复杂度为O(mn^2)，空间复杂度为O(mn)。其实，上述算法中，计算b[i][j]时，只用到了数组b的第i-1行和第i行的值。因而，算法中只要存储数组b的当前行，不必存储整个数组。另一方面，的值可以在计算i-1行时预先计算并保存起来。计算第i行的值时不必重新计算，节省了计算时间和空间。因此，算法可继续改进如下：
[cpp]
//3d4-7 最大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++)
{
cout<
}
cout<
cout<<"数组a的最大连续子段和为:"<
}
int MaxSum(int m,int n,int *a)
{
if(n
return 0;
int *b = new int[n+1];
int *c = new int[n+1];
b[0] = 0;//b数组记录第i行的最大i子段和
c[1] = 0;//c数组记录第i-1行的最大i-1子段和
for(int i=1; i<=m; i++)
{
b[i] = b[i-1] + a[i];
c[i-1] = b[i];
int max = b[i];
//n-m+i限制避免多余运算，当i=m时，j最大为n，可据此递推所有情形
for(int j=i+1; j<=i+n-m;j++)
{
b[j] = b[j-1]>c[j-1] b[j-1]+a[j]:c[j-1]+a[j];
c[j-1] = max;//预先保存第j-1行的最大j-1子段和