做网站的属于什么岗位,培训机构seo,网站在线做照片,iis网站架设教程题目#xff1a;从m*n矩阵中找出元素和最大的子矩阵。 分析#xff1a;此题是可看做节课求和值最大子数组的一种延伸。但如果按之前的枚举法显然太过麻烦#xff0c;复杂度为O#xff08;n^4#xff09;。那么有没有更好的方法呢#xff1f; 我们拿出上一道题做了进一步的…题目从m*n矩阵中找出元素和最大的子矩阵。 分析此题是可看做节课求和值最大子数组的一种延伸。但如果按之前的枚举法显然太过麻烦复杂度为On^4。那么有没有更好的方法呢 我们拿出上一道题做了进一步的商讨。找了一些网上的思路得到了如下方法 1 #include iostream.h2 maxSubarray(int n,int a[])3 {4 int b0,sum-100000;5 for(int i0;in;i)6 {7 if(b0) ba[i];8 else ba[i];9 if(bsum) sumb;
10 }
11 return sum;
12 }
13 int main()
14 {
15 int a[]{-1,3,4,-6,5,3,7,-9,10,0};
16 coutmaxSubarray(10,a)endl;
17 } 此算法的原理是按序一个个相加正数越加越大每得到一个正数更新一次sum而负数越加越小当和值为负时放弃前面的数更新b寻找新一轮的正数最大和b当大于前面的sum时赋给sum。for循环执行一遍将最大值在bsum之间动态传递和更新时间复杂度On与之前的穷举法相比无疑是一种高效的算法。 那么由此延伸到二维数组中求矩阵的最大子矩阵和我们得到如下算法 1 #include iostream.h2 int maxSubArray(int n,int a[])3 {4 int b0,sum-10000000;5 for(int i0;in;i)6 {7 if(b0) ba[i];8 else ba[i];9 if(bsum) sumb;
10 }
11 return sum;
12 }
13 int maxSub(int n,int array[][10])
14 {
15 int i,j,k,max0,sum-100000000;
16 int b[10];
17 for(i0;in;i)
18 {
19 for(k0;kn;k)//初始化b[]
20 {
21 b[k]0;
22 }
23 for(ji;jn;j)//把第i行到第j行相加,对每一次相加求出最大值
24 {
25 for(k0;kn;k)
26 {
27 b[k]array[j][k];
28 }
29 maxmaxSubArray(k,b);
30 if(maxsum)
31 {
32 summax;
33 }
34 }
35 }
36 return sum;
37 }
38 void main()
39 {
40 int n,array[10][10];
41 cout输入矩阵行列数;
42 cinn;
43 cout\n输入矩阵endl;
44 for(int i0;in;i)
45 {
46 for(int j0;jn;j)
47 {
48 cinarray[i][j];
49 }
50 }
51 cout子矩阵元素和最大为maxSub(n,array)endl;
52 } 转载于:https://www.cnblogs.com/candy-yyn/p/3627067.html
