首页 > 其他 > 详细

求最大子矩阵

时间:2014-03-27 17:48:24      阅读:272      评论:0      收藏:0      [点我收藏+]

                                                                             求二维矩阵最大子矩阵 

                                                                                                                              张纯,黄思思

 

算法思路:

 

1.遍历矩阵a[i][j]所有元素分别保存为子矩阵的第一个元素,在此基础上遍历找出子矩阵的最后一个元素,保证第一个元素的横纵坐标小于最后元素的横纵坐标。

 

2.定义sum=a[0][0]分别计算子矩阵的值,如果矩阵值大于sum,将子矩阵的值赋给sum,并保存第一个元素和最后元素的坐标值。最后得到的sum即为最大子矩阵的值。

 

 

 

代码示例:

 

 

#include<iostream.h>

int a1=0,b1=0,c1=0,d1=0;

void count(int a[][4],int i,int j,int p,int q,int &sum1)

{

 

int sum=0;

for(int b=i;b<=p;b++)

for(int c=j;c<=q;c++)

{

sum=sum+a[b][c];

}

if(sum>sum1)

{

sum1=sum;

a1=i;b1=j;c1=p;d1=q;

 

}

}

 

int main()

{

int sum1;

    

int a[3][4]={1,2,-3,4,-3,-1,9,23,-10,5,30,-5};

for(int i=0;i<3;i++)

for(int j=0;j<4;j++)

for(int p=i;p<3;p++)

for(int q=j;q<4;q++)

{

count(a,i,j,p,q,sum1);

}

    cout<<"最大子矩阵的值为:"<<sum1<<endl;

cout<<"最大子矩阵第一个元素的坐标为:"<<"("<<a1<<","<<b1<<")"<<endl;

cout<<"最大子矩阵最后元素的坐标为:"<<"("<<c1<<","<<d1<<")"<<endl;

return 0;

}

 

 

算法缺点:

 

1.采用穷举暴力求解,时间复杂度较高,为on^6;

求最大子矩阵,布布扣,bubuko.com

求最大子矩阵

原文:http://www.cnblogs.com/hsslove/p/3628665.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!