題目：從m*n矩陣中找出元素和最大的子矩陣。

分析：此題是可看做節(jié)課求和值最大子數(shù)組的一種延伸。但如果按之前的枚舉法顯然太過(guò)麻煩，復(fù)雜度為O（n^4）。那么有沒(méi)有更好的方法呢？

我們拿出上一道題做了進(jìn)一步的商討。找了一些網(wǎng)上的思路得到了如下方法：

1 #include <iostream.h> 2 maxSubarray(int n,int a[]) 3 { 4 int b=0,sum=-100000; 5 for(int i=0;i<n;i++) 6 { 7 if(b>0) b+=a[i]; 8 else b=a[i]; 9 if(b>sum) sum=b; 10 } 11 return sum; 12 } 13 int main() 14 { 15 int a[]={-1,3,4,-6,5,3,7,-9,10,0}; 16 cout<<maxSubarray(10,a)<<endl; 17 }

? ? ? 此算法的原理是，按序一個(gè)個(gè)相加，正數(shù)越加越大，每得到一個(gè)正數(shù)更新一次sum；而負(fù)數(shù)越加越小，當(dāng)和值為負(fù)時(shí)，放棄前面的數(shù)，更新b，尋找新一輪的正數(shù)最大和b，當(dāng)大于前面的sum時(shí)賦給sum。for循環(huán)執(zhí)行一遍，將最大值在b，sum之間動(dòng)態(tài)傳遞和更新，時(shí)間復(fù)雜度O（n），與之前的窮舉法相比無(wú)疑是一種高效的算法。

? ? ?那么由此延伸到二維數(shù)組中，求矩陣的最大子矩陣和，我們得到如下算法：

1 #include <iostream.h> 2 int maxSubArray(int n,int a[]) 3 { 4 int b=0,sum=-10000000; 5 for(int i=0;i<n;i++) 6 { 7 if(b>0) b+=a[i]; 8 else b=a[i]; 9 if(b>sum) sum=b; 10 } 11 return sum; 12 } 13 int maxSub(int n,int array[][10]) 14 { 15 int i,j,k,max=0,sum=-100000000; 16 int b[10]; 17 for(i=0;i<n;i++) 18 { 19 for(k=0;k<n;k++)//初始化b[] 20 { 21 b[k]=0; 22 } 23 for(j=i;j<n;j++)//把第i行到第j行相加,對(duì)每一次相加求出最大值 24 { 25 for(k=0;k<n;k++) 26 { 27 b[k]+=array[j][k]; 28 } 29 max=maxSubArray(k,b); 30 if(max>sum) 31 { 32 sum=max; 33 } 34 } 35 } 36 return sum; 37 } 38 void main() 39 { 40 int n,array[10][10]; 41 cout<<"輸入矩陣行列數(shù)"; 42 cin>>n; 43 cout<<"\n輸入矩陣"<<endl; 44 for(int i=0;i<n;i++) 45 { 46 for(int j=0;j<n;j++) 47 { 48 cin>>array[i][j]; 49 } 50 } 51 cout<<"子矩陣元素和最大為"<<maxSub(n,array)<<endl; 52 }

轉(zhuǎn)載于:https://www.cnblogs.com/candy-yyn/p/3627067.html

總結(jié)

以上是生活随笔為你收集整理的软工随堂练 找出和值最大的子矩阵 尹亚男 赵静娜的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。