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

2470 阅读 6 评论 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分

18 人评分

本文分类：题解列表
浏览次数：2470 次浏览
发布日期：2020-03-26 13:24:22
本文链接：https://blog.dotcpp.com/a/68542

上一篇 > 蓝桥杯基础练习-十进制转十六进制-题解(C++代码)
下一篇 > [编程入门]求和训练-题解(C语言代码)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

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

评论列表共有 6 条评论

发表评论取消回复

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

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 6 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 6 条评论

发表评论取消回复