快乐在明天

用户名：dotcpp0598211

访问量：1674

签　名：

等　　级
排　　名	498
经　　验	4598
参赛次数	0
文章发表	14
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

数学解牛吃牧草
浏览：840

计算多项式的值（注意事项）
浏览：104

2750: 字符菱形
浏览：306

你可能喜欢

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

最大子矩阵暴力解O（n4）和优化解 O（n3）

　　作者: 快乐在明天　　　　发表时间：2023-04-02 10:46:51 浏览：61　|　评论：0　

原题链接：最大子矩阵

解题思路:   双指针加二维数组前缀和 注意事项: 参考代码:                    //原始做法  纯暴力                      #include<iostream>                     #include<cmath>                    using namespace std;                    typedef long long ll;                     const int N=1e3+5;                    int g[N][N],s[N][N];                    int n,m,x;                    int maxn=-128;                     int main()                    {                        	cin>>n;                        	for(int i=1;i<=n;i++)                        	{                            		for(int j=1;j<=n;j++)                            		{                            			cin>>g[i][j];                            			//二维数组前缀和处理 s数组记录二维数组前缀和                             			s[i][j]=g[i][j]+s[i][j-1]+s[i-1][j]-s[i-1][j-1];                            		}                        	}                    	    ll sum=0;                        	//利用两个双指针  用j指向i控制行的变化 用r指向l控制列的变化                        	//画图理解,相当于看区域(i,l)到(j,r)的前缀和是否小于等于x,如果                        	//满足则说明该矩阵符合条件,矩阵大小为(j-i)*(r-l)                         	//这样可以得到满足条件的矩阵的大小和个数(大小从n*m到1*1)                         	for(int i=1;i<=n;i++)                        	{                            		for(int j=i;j<=n;j++)                            		{                                			for(int l=1;l<=n;l++)                                			{                                    				for(int r=l;r<=n;r++)                                    				{                                    					//i和j控制着矩阵的宽,l和r控制矩阵的长,相当于求                                    					//(i,l)到(j,r)的前缀和,通过遍历所有矩阵的大小,来                                    					//筛选符合条件的矩阵大小个数                                         				    sum=s[j][r]-s[i-1][r]-s[j][l-1]+s[i-1][l-1];                                            					if(maxn<sum)                                             {                                                 maxn=sum;                                              }                                        }                                			}                            		}                    	}                    	cout<<maxn<<endl;                    	return 0;                     }  //优化解法，利用前缀列和 和双指针                    #include<iostream>                    using namespace std;                    const int N=1e3+3;                    int g[N][N],s[N][N];                    int n;                     int maxn=-128;                                         int main()                    {                        	cin>>n;                        	for(int i=1;i<=n;i++)                        	{                            		for(int j=1;j<=n;j++)                            		{                                			cin>>g[i][j];                                			s[i][j]=s[i-1][j]+g[i][j];                            		}                         }                          for(int i=1;i<=n;i++)                          {                                for(int j=i;j<=n;j++)                                {                                     //重点 每次循环前ans都要重置 如果不清0则每次循环都包含重复值                                     			int ans=0;                                    			for(int k=1;k<=n;k++)                                    			{                                        				ans+=s[j][k]-s[i-1][k];                                        				if(maxn<ans)                                        				{                                            					maxn=ans;                                        				}                                         //如果ans小于0 那么以后ans再加其他数总要减小，所以ans要重置                                         				if(ans<0)                                        				{                                            					ans=0;                                        				}                                			}                            		}                        	}                    	cout<<maxn<<endl;                    	return 0;                     }

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

快乐在明天

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

用筛法求之N内的素数。（C语言代码）

【回文数(二)】（C++代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

最大子矩阵暴力解O（n4）和优化解 O（n3）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）from DQM

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

时间转换（C语言代码）

简单的a+b （C语言代码）

快乐在明天

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

【回文数(二)】 （C++代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

最大子矩阵 暴力解O（n4） 和优化解 O（n3）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）from DQM

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

时间转换 （C语言代码）

简单的a+b （C语言代码）

用筛法求之N内的素数。（C语言代码）

【回文数(二)】（C++代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

最大子矩阵暴力解O（n4）和优化解 O（n3）

　　评论区

时间转换（C语言代码）