C语言网奉行“学练同步，知行合一”的学习理念，希望大家都能理论与动手一起加强！拒绝理论派！
每月月赛，最后一个周六晚八点开始，请提前预约参赛，参与排名！
混一天和努力一天，一天看不出任何差别，三天看不到任何变化，七天也看不到任何距离……
但是一个月后会看到话题不同，三个月后会看到气场不同，半年后会看到距离不同，一年后会看到人生道路截然不同。
通知：举办比赛权限已经完全开放，支持老师、个人随时抽题创建校内赛等比赛，达到P2级即可
比赛名称建议包含学校/组织名称，具有辨识度。不友好名称可能会被屏蔽，请大家知晓！
肺炎疫情，努力学习就是对社会最大的贡献！
题库的题不仅仅支持C语言C++、java，Python和php也可以提交
编程小组功能上线！欢迎各位老师、社团协会小组负责人申请创建，方便教学、训练！
申请优质题解的标准第一，代码格式工整整齐，第二，不少于300字的思路讲解，有配图更佳！
代码格式工整、有详细说明和配图的题解才有更多的浏览哦
学习交流 QQ1群156740915、4群 364137421、 211300176、博主群487133400 Python小组群 783851273 验证信息备注网站昵称！
个人资料中有关于自己联系地址、联系电话的信息，用于我们邮寄奖品福利等，且信息不会公开，别人看不到，请大家知晓！
比赛创建功能已经完全开放，需要达到P2等级，写博客要达到P2等级
注意，恶意创建比赛、直接复制代码发布无营养题解的行为，将被禁止相应权限！并扣除经验值! 申请恢复请联系管理员解除
本站题解请在题目内页-我要写题解发布，这样可以出现在题目题解列表页，还可以申请加优增加曝光哦！

李华

用户名：2645479600

访问量：2372

签　名：

qq:2645479600，欢迎共同探讨

等　　级
排　　名	597
经　　验	2364
参赛次数	2
文章发表	22
年　　龄	20
在职情况	学生
学　　校	广大华软
专　　业	电子信息工程

　　自我简介：

C/C++程序设计蓝桥杯新人，欢迎探讨

TA的其他文章

[蓝桥杯][历届试题]九宫重排-题解(C语言 with STL)---简略、详细思路都有。初学者可以看看
浏览：175

[蓝桥杯][基础练习VIP]2n皇后问题-题解(C语言代码)--------详细带图解释皇后系列问题，适合新人
浏览：481

[蓝桥杯][基础练习VIP]回形取数-题解(C++代码)-----深度优先搜索
浏览：49

你可能喜欢

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）
浏览：553

C语言程序设计教程（第三版）课后习题8.6 （C++代码）不是所有的时候都要按照题目要求才能AC
浏览：1160

【C语言训练】排序问题<2> （C++代码）（sort函数）
浏览：824

点我有惊喜！你懂得！
浏览：1735

P1002 （C语言代码）
浏览：756

[蓝桥杯][历届试题]最大子阵-题解(C语言代码)---dp最大子段和思想（详细）

　　作者: 李华　　　　发表时间：2020-03-26 13:24:22 浏览：54　|　评论：0　

原题链接：[蓝桥杯][历届试题]最大子阵

解题思路:
###### //建议边看代码边看思路//
1.如果单纯枚举首行，末行，首列，末列来做这道题，就是四重循环，数据最大时，每重循环大概500次，500^4时间复杂度可以达到十的十次方，肯定会超时。所以要考虑能否降循环，或者找到贪心，dp规律。
2.我们思考一下，可以发现。我们可以开一个数组sum，用来记录某个格子头上全部的格子+它本身的和。举个例子，样例的数据是
-1 -4 3
 3  4 -1
 -5 -2 8
 那么sum数组就是
 -1 -4 3
 2 0 2
 -3 -2 10
 /*sum数组的建立看代码13~24行*/
 3.建立起sum数组之后，sum的每个元素就代表该列从第一个元素到其自身的和。比如sum数组‘0’这个格子，就是样例数组第二列从第一个元素加到这个位置的和，-4+4=0。‘10’这个格子=3+(-1)+8，其它同理
 4.为什么要求这个sum数组？因为我们可以通过这个sum数组求出原数组中任意一列的任意一行元素到任意一行元素的和。比如我要求第一列中，第二行到第三行的和。
 这个和=sum【3】【1】-sum【2-1】【1】
所以和=-3-(-1)=-2
###### 仔细看，式子中的2需要减1，第三行减去第二行头上一格得到的结果就是第二行到第三行的和
5.枚举首行，末行，当前考虑的列尾。不需要四重循环。三重循环就可以一一列举各种情况了。用最大子段和的思想求出某种首行末行时，以这个元素为列尾得到的最优和。全部的最优和里面最大的就是结果。（所谓最大字段和就是前面小于0就舍弃，大于0就加上，不明白的话可以私信）
//有错误或者疑问可以私信或者评论//
```c
#include <stdio.h>
int n,m,a[505][505],sum[505][505],now,max_sum=-999999999,temp_ans;	//sum数组用来记录某个格子，其头上全部格子的和 
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);	//读入数据 
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(i==1)
			{
				sum[i][j]=a[i][j];
				continue;
			}
			sum[i][j]=sum[i-1][j]+a[i][j];
		}
	}
	for(int first=1;first<=n;first++)	//枚举首行 
	{
		for(int last=first;last<=n;last++)	//枚举末行，末行不能比首行小，故初值为first
		{
			for(int c=1;c<=m;c++)	//枚举列的结尾 
			{
				now=sum[last][c]-sum[first-1][c];	//在首行~末行中，某列的和
				if(temp_ans>=0)	//如果前面的和大于等于0，就将它加上
				{
					temp_ans=now+temp_ans;
					if(temp_ans>max_sum)	max_sum=temp_ans;	//尝试能否更新最大值
				}
				else if(temp_ans<0)	//如果前面的和小于0，舍弃它
				{
					temp_ans=now;
					if(temp_ans>max_sum)	max_sum=temp_ans;	//尝试能否更新最大值 
				} 
			} 
			temp_ans=0;
		} 
	} 
	printf("%d",max_sum); 
	return 0;
}
```

0.0分

4 人评分

C语言网提供「C语言、C++、算法竞赛、真题百练、Python课程」在线课程，全部由资深研发工程师或ACM金牌大佬亲授课，更科学、全面的课程体系，以在线视频+在线评测的学习模式学习，学练同步，拒绝理论派，真正学会编程！还有奖学金等增值福利等你！

　　评论区

精彩推荐

【蟠桃记】（C语言代码）浏览：484

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）浏览：169

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）浏览：540

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）浏览：458

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）浏览：290

printf基础练习2 （C语言代码）浏览：582

最小公倍数（C语言代码）浏览：462

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

A+B for Input-Output Practice (V) （C语言代码）浏览：358

有关字符，字符串的输入输出函数说明浏览：345