日期:2014-05-18 浏览次数:20902 次
题:求一个矩阵中最大的二维子矩阵(元素和最大).如: 1 2 0 3 4 2 3 4 5 1 1 1 5 3 0 中最大的是: 4 5 5 3 要求:(1)写出算法;(2)分析时间复杂度;(3)用C写出关键代码 分析:方法一、这是最容易想到也是最容易实现的方法。遍历矩阵(行迭代器为i,列迭代器为j),以当前遍历到的元素为首a[i,j],计算二维子矩阵的和(sum=a[i,j]+a[i+1,j]+a[i,j+1]+a[i+1,j+1]),并找出和最大的二维矩阵,注意矩阵的最后一行和最后一列不用遍历。时间复杂度为O(i*j)。 实现代码: void get_max_22Matrix(int *a,int row,int col,int *result) //a为原矩阵,row,col指a矩阵的行和列,result存储最终得到的子二维矩阵 { int maxsum=0,result_i,result_j,sum; #define a(i,j) *(a+(i)*col+(j)) //用二维的形式表示一维数组,访问需要一定的代价 #define result(i,j) *(result+(i)*2+(j)) for(int i=0; i<row-1; i++) for(int j=0; j<col-1; j++) { sum = a(i,j)+a(i+1,j)+a(i,j+1)+a(i+1,j+1); //访问四个元素并相加得到当前的和 if(maxsum<sum) //更新最大子二维矩阵数据 { maxsum = sum; result_i = i; result_j = j; } } /* 将结果存储到result二维数组中*/ result(0,0)=a(result_i,result_j); result(1,0)=a(result_i+1,result_j); result(0,1)=a(result_i,result_j+1); result(1,1)=a(result_i+1,result_j+1); #undef a #undef result }