【rqnoj106】最大加权矩形(最大子矩阵和问题)

2013年12月2日2,1360

给定一个长度为n的一维的数组matrix[n],让求其最大matrix[i] + matrix[i+1] + … + matrix[j] = sum问题?

 

简单算法:

穷举法

先预处理map[n]表示从matrix[0]->matrix[n]的和

for(int i = 0 to n)

for(int j = i+1 to n)

{

int tmp = map[j] – map[i-1];
}

算法时间复杂度为O(n^2).

空间额外占据O(n)。

 

DP算法:

设max[j]为matrix[0….j]中的最大子段之和,max[j]当前只有两种情况:

1)最大子段一直连续到matrix[j]; (2)以matrix[j]为起点的子段。

注意!
如果当前最大子段没有包含matrix[j],如果没有包含的话,在算max[j]之前我们就已经算出来了。

得到max[j]的状态转移方程为:max[j] = max { max[j-1] + matrix[j], matrix[j]}

所求的最大子段和为max{ max[j], 0<=j<n}

进一步,我们可以将max[]数组用一个变量代替。因为每次计算max[i]之需要用到上一个max[i-1],故一个变量可以替代。

空间优化至O(1)

 

max = – (1<<31);

tmp = 0;

 

for(int i=1 to n)

{

if(tmp>0)

tmp += matrix[i];

else

tmp = matrix[i];

if(tmp>max)

max = tmp;
}

 

 

————————————————————–

 

给定一个二维的数组matrix[n][n],让求其最大子矩阵和问题?

 

原始算法:

遍历每一个子矩阵,左上角为[x,y],右下角为[c, r],可知子矩阵共有O(n^4);

而每个子矩阵算总和的算法复杂度为O(n^2);

 

—->原始算法复杂度为o(n^6),时间复杂度太高,但是却无额外空间。

 

改进算法二:

遍历每一个子矩阵,左上角为[x, y],右下角为[c, r],子矩阵共有O(n^4);

但是每个子矩阵算和,时间复杂度可以优化为O(1)。

利用到额外空间map[n][n],其中map[x][y]表示左上角为[0, 0],右下角为[x, y]的子矩阵和。

 

左上角为[x, y],右下角为[c, r],子矩阵的和 = map[c][r] – map[x-1][r] – map[x][r-1] + 2*map[c-1][r-1]。

时间复杂度总共为O(n^4);

额外空间O(n^2)。

 

改进算法三:

利用额外空间O(n^3),记录子矩阵map[i][j][y],第y列的第i行到第j行的和。

 

1)以i行开始,j行结束的子矩阵,总共有n个。计算每个子矩阵的算法复杂度为O(1)。

 

2)i行开始,j行结束。2变量,两个变量,复杂度为O(n^2)。

 

可知该算法可以用O(n^3)的时间复杂度算出,但其代价是空间复杂度也是O(n^3)。

 

 

改进算法四:

相比算法三,仅是优化了空间复杂度,将其降低为O(n^2)。

 

子矩阵和map[x][y]表示第y列从第1行到第i行的和。

 

算法三的map[i][j][k] =  map[j][k] – map[i-1][k]即可。不用都记录下来

 

参考代码