求二维矩阵最大子矩阵
张纯,黄思思
算法思路:
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.采用穷举暴力求解,时间复杂度较高,为o(n^6);
原文:http://www.cnblogs.com/hsslove/p/3628665.html