最大子段和问题什么意思(最大子段和动态规划)

从今天开始呢,我们就正式开始数据结构的学习了,可以说,这是计算机专业中最为核心的一门课程,也是最为重要的一块内容。 这一部分,是企业招聘时最为看重的一部分,也是大家解决算法实现逻辑最为重要的一部分,更是帮助大家找到一份好工作的重要筹码。 我们今天的这道题呢,就是解决“最大子列和问题”。 给定K个整数组成的序列{N1,N2,…,NK},“连续子列”被定义为{Ni,Ni+1,…,Nj},其中1…

从今天开始呢,我们就正式开始数据结构的学习了,可以说,这是计算机专业中最为核心的一门课程,也是最为重要的一块内容。

这一部分,是企业招聘时最为看重的一部分,也是大家解决算法实现逻辑最为重要的一部分,更是帮助大家找到一份好工作的重要筹码。

我们今天的这道题呢,就是解决“最大子列和问题”。

给定K个整数组成的序列{N1,N2,…,NK},“连续子列”被定义为{Ni,Ni+1,…,Nj},其中1<=i<j<K,而“最大子列和”则是找到一个所有连续子列元素的和中的最大值。

比方说给定一组序列为{-2,11,-4,13,-5,-2},其中连续子序列{11,-4,13}则是最大值为20。

那么最终打印输出的结果则为20。

C语言解决“最大子列和问题”,数据结构由此开始(第一节)

梳理逻辑

对于函数题,特别是解决数据结构与算法题的时候,一定要静下心来,然后梳理清楚题目的逻辑,当然了,现在不太会也很正常,完全可以慢慢来,但是如果要找工作的话,那可得加把劲了。

1、输入第一行给出正整数K(<=100000),用到一个scanf函数来输入。

2、第二行给出K个整数,因为我们是一个序列,所以用到的是数组。

3、最麻烦的则是找出最大和的子序列,我们可以这样来理解:

先从数组中的第一个元素开始加起,找到包含第一个元素的所有子序列的和,并比较大小。

然后找出最大值的和,记录下来。

与此同时,下一次循环遍历的时候就把这个和清零,但是最大值不变。

依次继续求和,并与最大值比较大小,记录下相对较大的那个值。

在所有循环都结束后,最终的那个最大值则是我们要求的最大值。

C语言解决“最大子列和问题”,数据结构由此开始(第一节)

代码实现

//最大子列和问题
#include<stdio.h>
int main(){
	int K;//给出正整数K
	int M[100000];//给出K个整数
	int count;//计数法
	int SUM = 0;//遍历求和
	int MAX = 0;//初始的最大值为0
	scanf(\"%d\", &K);
	for(int i=0;i<K;i++){
		scanf(\"%d\",&M[i]);
		if(M[i]<0){
			count++;
		}
	}
	if(count==K){//所有的数都是0的情况下
		printf(\"0\");
	}
	for(int i = 0; i < K; i++){
		//从元素1开始
		SUM = 0;//每次循环求和的时候,求和都要变为0才行
		for(int j = i; j < K; j++){
			SUM = SUM + M[j];
			if(SUM > MAX){
				MAX = SUM;
			}
		}
	}
	printf(\"%d\",MAX);

}

结果测试

C语言解决“最大子列和问题”,数据结构由此开始(第一节)
C语言解决“最大子列和问题”,数据结构由此开始(第一节)

总结

这道数据结构题,可以说是数据结构章节中最为简单的一道题目了,有难度的还在后面呢,我研究生快毕业了,也知道自己得快速提升实力了,秋招末班车以及春招开启,一定要赶上,冲!!!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

(0)
上一篇 2022年5月6日 上午10:28
下一篇 2022年5月6日 上午10:30

相关推荐

  • pdf文件怎么解密,pdf 在线解密方法

    有时我们从某些网站上下载下来一些PDF文件,其中有些PDF文件无法打开阅读,或者我们想要对PDF文件进行打印或编辑等操作的时候提示我们需要输入口令密码之类的权限,非常不方便我们的使用,那么有没有什么办法可以取消PDF文件的密码呢?PDF文件怎么解密? 首先,如果某个PDF文件的密码是你为了保护自己的PDF文件而创建的,但过后想要取消文件加密,有些朋友只会加密而不会取消加密的话,该怎么办呢? 我们用…

    2022年6月4日
    610
  • 省电空调推荐,五款质量好又节能的空调品牌推荐

    无论是夏天还是冬天,家用空调总是最繁忙的家电之一,当下空调已经融入到每一个家庭的生活中,是不可或缺的一部分。所以能耗低成为众多厂家吸引用户的重要卖点之一。但是用户面对市面上五花八门空调,再加上许多“一晚一度电”等不符实的广告,想要购买空调的朋友们难免会有些眼花缭乱,不知道什么样的空调才是自己需要的,这次就为大家推荐几款低能耗大匹数空调,既省电又能轻松搞定冬夏难熬季节。 格力KFR-35GW/(35…

    2022年9月11日
    540
  • 哪个牌子净水器质量好,家用净水器十大品牌

    净水器哪个牌子好?净水器十大品牌排名是怎样的?净水器价格是多少呢?如果大家看到这三个问题时,正好是自己正在困惑的问题,同时自己也正在寻找答案,那么就请接着往下看,接下来七星舒适家居小编将会介绍给大家,相信你看完文章后会学习有所收获。 首先七星将会给大家介绍净水器哪个牌子好的问题。针对不同家庭的需求和价格接受能力,就会有不同的净水器牌子,如果一定要问净水器哪个牌子好的话,那么则是在净水器行业一直领先…

    2022年9月3日
    740
  • 企业怎么宣传推广品牌,宣传品牌的方法与优势

    一、品牌定位/创建要明确 对于品牌推广来说,品牌定位的准确与否,直接关系到推广的效果。品牌定位,就是为了结合自身的现状、优势、愿景等确定行业、市场。品牌是做什么行业,在行业中要做到什么程度,是做国内市场还是国外市场,通过什么方式去销售,产品针对的消费者是低端、中端还是高端的。做品牌定位,一定要有格局,打算为哪些人提供服务,产品满足哪些人的需求,只有满足了目标消费者的需求,并做好口碑。 二、品牌价值…

    2022年6月20日
    710
  • 哪里能看美剧,中国两个最大美剧站app

    今天小科给大家分享几款看美剧的软件,应该是仅存的几款,希望对大家有所帮助。 1、可乐美剧 软件内存十分的小,不到10M,界面也十分美观简洁。 测试手机:小米6 软件试用 首先点击搜索 然后选择你喜欢的电影 之后保存到百度云,就可以播放了。 2、必看 软件内存16.81M,测试手机:小米6 软件可以观看日剧和美剧,依靠第三方网页在线播放和百度云播放。 缺点:广告,在线播放,横屏播放有bug 具体试用…

    2022年8月18日
    870
  • 卫龙辣条干净吗,带你走进辣条界的一哥世界

    卫龙凭什么统治了500亿的辣条江湖? 日前一网友“购买的卫龙辣条火锅吃出虫子”的爆料,引发了全网的吐槽。 可即使被吐槽,卫龙依然稳坐“辣条界一哥”之位。 【曾为辣条业除“黑”】 从2014年网络上疯传卫龙的全自动化生产车间宣传片开始,卫龙就成了辣条界的标杆。 虽是纯正的“民族零食”,但辣条产品出现不过二十年,主要原料就是日常所见的面粉之列。正因原料简单、无技术壁垒,早期辣条生产门槛极低,大量小作坊…

    2022年8月26日
    1440
  • 能力素质模型包括哪些方面,史上最全的能力素质模型资料

    随着经济全球化的发展和知识经济时代的来临,人才在竞争中起着决定性的作用越发明显。如今许多企业都在积极寻找和挖掘产生高绩效的管理者的能力特征,构建管理者的“素质能力模型”,从而有针对性地选拔和培育适合企业成长和发展的优秀领导人才。 那么,企业高绩效管理者通用“素质能力模型”有哪些内容?下面楚柳香小编就和大家一起来探讨一下吧! 一、素质能力与技能 1、素质能力决定工作绩效的持久品质与特征。 2、技能对…

    2022年8月4日
    580
  • 天猫京东价格差距那么大,解说天猫和京东商城的主要区别

    618大战刚刚过去,京东和天猫在此次战役中打的不亦乐乎,相必大家对二者都挺熟悉的,但是二者真正的差异究竟在哪里呢? 1.物流 物流这一块无疑是京东胜出,京东也是一直以自己的物流为特色,在每年促销战开始前夕,就拿物流开涮其他网站,不容怀疑,京东的物流确实做得很棒,天猫近几年也在做菜鸟,但是已经被京东甩了一大截了 2.商品 京东商品大部分都是自营,像是一个大超市,有自营商品也有一些事第三方卖家的,自营…

    2022年8月6日
    860
  • 微信怎么导出聊天记录,微信文件批量导出教程

    微信出了新功能:聊天记录“不显示”。 渣男们第一时间更新,并隐藏了各种不堪入目的对话框。 有句话说得好,“好男人都是相似的,渣男却各有各的渣”。 今天兔姐就给大家揭露——渣男十大常见骚操作,希望各位姐妹擦亮眼睛! 林子大了,什么渣男都有。 但遇到渣男不可怕,可怕的是不能及时止损,任其继续伤害你。 所以,对待渣男的正确方式就是:果断说拜拜

    2022年6月22日
    740
  • 5寸智能手机推荐(5寸左右的全面屏手机)

    在小米重新定义了全面屏手机之后,可以说这个词语,成为了这几年最为风靡的关键词。而随着竞争的日益激烈,可以说,除了在性能、硬件配置和UI等方面,各大手机厂商不断努力争夺之外,一些特定的用户群体,比如老人用户、学生用户,也成为了关注的重点。 但是,真正做到令老人和学生用户满意的,其实并不多。因为年龄的因素,想要让老人和学生去真正适应智能手机的全部功能,是不现实的。其实,只要把握住几个关键点,让手机更贴…

    2022年5月6日
    1800

发表回复

登录后才能评论

联系我们

400-800-8888

在线咨询: QQ交谈

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息

关注微信