每日微软面试题――day 8(最大的二维子矩阵) - 花心龟 cabin - 博客频道 - CSDN.NET

每日微软面试题――day 8(最大的二维子矩阵) - 花心龟 cabin - 博客频道 - CSDN.NET
题：求一个矩阵中最大的二维子矩阵(元素和最大).如:
          1 2 0 3 4
          2 3 4 5 1
          1 1 5 3 0
          中最大的是: 
          4 5
          5 3

一、增加一个变量，last_vsum（叫做“最新纵向和”，v是vertical） 且初始化为last_vsum = a[0,0]+a[1,0]，其作用将在下面说明。

二、改变遍历方式，原先每次访问四个元素，现在变为每次访问纵向的两个元素（a[i,j],a[i+1,j]），横向遍历，遍历的起始点改为第二个元素，终点到最后一个元素。

三、改变求和方式，求和方法是：首先将上一次保存的和last_vsum加进sum中，再将last_vsum更新为当前纵向的两个元素a[i,j],a[i+1,j]之和，然后再将last_vsum加入sum中，这样就得到本次二维矩阵的和可与maxsum进行比较。如此每次求和只需访问两个元素a[i,j],a[i+1,j]。

void get_max_22Matrix(int *a,int row,int col,int *result)
{
  int maxsum=0,result_i,result_j,sum,last_vsum=0;
  
#define a(i,j) *(a+(i)*col+(j))  
#define result(i,j) *(result+(i)*2+(j))
  
  last_vsum = a(0,0)+a(1,0);  //初始last_vsum
  for(int i=0; i<row-1; i++)
    {
     for(int j=1; j<col; j++)
   {
     sum = last_vsum ;  //将last_vsum加入sum
     last_vsum = a(i,j)+a(i+1,j);//更新last_vsum
     sum += last_vsum;//将更新后的last_vsum再与sum累加，得到当前子二维矩阵的和
     if(maxsum<sum)
       {
         maxsum = sum;
         result_i = i;
         result_j = j-1;
       }
   }
    }
 
   /* 将结果存储到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
}

1.     public int[][] herizonalFind(int[][] a,int row,int col){  
2.         int[][] result=new int[2][2];  
3.         int lastHerizonalSum=a[0][0]+a[0][1];  
4.         int sum=0;  
5.         int p=0;  
6.         int q=0;  
7.         for(int i=1;i<row;i++){  
8.             for(int j=0;j<col-1;j++){  
9.                 int temp=lastHerizonalSum+a[i][j]+a[i][j+1];  
10.                 lastHerizonalSum=a[i][j]+a[i][j+1];  
11.                 if(temp>sum){  
12.                     sum=temp;  
13.                     p=i;  
14.                     q=j;  
15.                 }  
16.             }  
17.         }  
18.         result[0][0]=a[p-1][q];  
19.         result[0][1]=a[p-1][q+1];  
20.         result[1][0]=a[p][q];  
21.         result[1][1]=a[p][q+1];  
22.         return result;  
23.     }  
24.       
25.     public int[][] verticalFind(int[][] a,int row,int col){  
26.         int[][] result=new int[2][2];  
27.         int lastVerticalSum=a[0][0]+a[1][0];  
28.         int sum=0;  
29.         int p=0;  
30.         int q=0;  
31.         for(int i=0;i<row-1;i++){  
32.             for(int j=1;j<col;j++){  
33.                 int temp=lastVerticalSum+a[i][j]+a[i+1][j];  
34.                 lastVerticalSum=a[i][j]+a[i+1][j];  
35.                 if(temp>sum){  
36.                     sum=temp;  
37.                     p=i;  
38.                     q=j;  
39.                 }  
40.             }  
41.         }  
42.         result[0][0]=a[p][q-1];  
43.         result[0][1]=a[p][q];  
44.         result[1][0]=a[p+1][q-1];  
45.         result[1][1]=a[p+1][q];  
46.         return result;  
47.     } 

方法一、这是最容易想到也是最容易实现的方法。遍历矩阵(行迭代器为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)。

1.     public int[][] brutalFind(int[][] a){  
2.         int[][] result=new int[2][2];  
3.         int row=a.length;  
4.         int col=a[0].length;  
5.         int sum=0;  
6.         int p=0;  
7.         int q=0;  
8.         for(int i=0;i<row-1;i++){  
9.             for(int j=0;j<col-1;j++){  
10.                 int x=a[i][j];  
11.                 int y=a[i][j+1];  
12.                 int z=a[i+1][j];  
13.                 int k=a[i+1][j+1];  
14.                 int temp=x+y+z+k;  
15.                 if(temp>sum){  
16.                     sum=temp;  
17.                     p=i;  
18.                     q=j;  
19.                 }  
20.             }  
21.         }  
22.         result[0][0]=a[p][q];  
23.         result[0][1]=a[p][q+1];  
24.         result[1][0]=a[p+1][q];  
25.         result[1][1]=a[p+1][q+1];  
26.         return result;  
27.     }  

Read full article from 每日微软面试题――day 8(最大的二维子矩阵) - 花心龟 cabin - 博客频道 - CSDN.NET