最大子矩阵问题

    最优子矩阵是建立在数列连续最大和的基础上的。所谓最优子矩阵，就是指在一个n*m二维的矩阵中，确定一个小的矩阵，使这个小矩阵中所有元素的和最大。

思考一下最优子矩阵和连续最大和的异同：

1、  所求的和都具有连续性；

2、  连续最大和是一维问题，最优子矩阵是二维问题

另外，对于一个矩阵而言，如果我们将连续k行的元素纵向相加，并对相加后所得的数列求连续最大和，则此连续最大和就是一个行数为k的最优子矩阵！由此，我们可以将二维的矩阵压缩成一维矩阵，转换为线性问题，从而求解。

 其实就是将二维的问题,换成一维

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 4 //matrix N*N


int getrand()
{
  int num = rand()%11-5;
  return num;
}

void print_matrix(int A[N][N])
{
  int i;
  int j;
  
  for(i=0;i<N;i++)
  {
   for(j=0;j<N;j++)
     printf("%d\t",A[i][j]);
   
   printf("\n");
  }
}

int max_sub_array(int B[], int n)
{
  int i = 0;
  int sum = 0;
  int max = 0;
  for(;i<n;i++)
   {
     sum += B[i];
     if(sum>max)
       max = sum;
     else if(sum<0)
       sum = 0;
   }
   return max;
}

int max_sub_matrix(int A[N][N])
{
  int i;
  int j;
  int k;
  int last_i = 0;
  int last_j = 0;
  int max = 0;
  int tmp = 0;
  
  int array[N];
 

  /*i=0,表示包含第一行的最大子矩阵 i=1...类推*/
  for(i=0;i<N;i++)
   {
     for(k=0;k<N;k++)
       array[k] = 0;
                  
     for(j=i;j<N;j++)
     {
      for(k=0;k<N;k++)
         array[k] += A[j][k];
    
      tmp = max_sub_array(array, N);
      if(tmp>max)
       {
        last_i = i;
        last_j = j;
        max = tmp;
       }
     }
   }
   /*最大子矩阵开始和结束的行*/
   printf("last_i is %d, last_j is %d\n",last_i+1, last_j+1);
   return max;
}

int main(int argc, char *argv[])
{
  int i;
  int j;
  int ret;
  int A[N][N];
  srand((unsigned int)time(NULL));
  
  for(i=0;i<N;i++)
   for(j=0;j<N;j++)
    A[i][j] = getrand();
  
  print_matrix(A);
  ret = max_sub_matrix(A);
  printf("max is %d\n",ret);
  system("PAUSE");    
  return 0;
}