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

从今天开始呢,我们就正式开始数据结构的学习了,可以说,这是计算机专业中最为核心的一门课程,也是最为重要的一块内容。 这一部分,是企业招聘时最为看重的一部分,也是大家解决算法实现逻辑最为重要的一部分,更是帮助大家找到一份好工作的重要筹码。 我们今天的这道题呢,就是解决“最大子列和问题”。 给定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

相关推荐

  • 手机丢了怎么找回,试试这个办法轻松帮你找回

    出门在外,一不小心,手机被盗,有资深被盗经验的小编,从一开始的慌里慌张到后来几次的镇定自若,都已经习惯走流程了~ 如果手机不幸“中招”了,你知道第一时间做什么吗?不是报警哦,我们来看下手机丢失后第一时间应该做什么紧急处理。 一、紧急处理 现在人手一部智能手机,里面有各种社交账号密码,支付宝、网上银行、微信、QQ……都在手机里!所以手机丢失后我们先做下面这些事! 1、挂失号码 第一时间致电各大手机运…

    2022年9月11日
    420
  • 苹果手机怎么备份,三种方法帮助你轻松完成备份

    iPhone备份麻烦,大家都知道!到底有多麻烦呢?以小编的经验,大概是折腾一晚上都不一定能顺利完成吧!因此,今天小编就要来跟大家分享一些常用靠谱的备份方法,学会了就再也不用担心数据意外丢失啦! 方法一:iPhone自带的备份工具iCloud 操作方法:点击打开设置,点击自己手机账户,点击进入iCloud。接着找到“iCloud云备份”功能进入后,开启该开关即可。 这样在iPhone接入电源、锁定且…

    2022年8月19日
    510
  • 刷手机排名是什么(揭秘App刷榜现场内幕)

    刷排行,刷销量,刷信誉,刷人气,似乎跟互联网有关系的都可以用“刷”来打造“爆款”,近日有媒体爆料鲜为人知的刷手机app商店排行榜,一份灰色产业链下的机械工作。 大冬天的,一个穿着羽绒服的妹纸,前面摆放着各种一排排大屏手机,目测下估计不下于75台,看来为了刷排行版也是蛮拼的。没有技术的苦力活,在丰厚的利润诱惑之下,让人趋之若鹜,重金之下必有勇夫,根据小道消息爆料,某刷榜公司价目表:刷榜分为冲榜和维护…

    2022年9月25日
    560
  • 门店营销培训资料,门店的销售技巧和话术课程分享

    门店是产生业绩的核心所在 提升门店业绩从提升“人”的能力开始 门店经营管理者的困惑 区域经理说: 我也想给店长培训,可除了讲产品,和公司制度外缺乏系统的思路; 店长说: 门店工作丰富繁杂,对上有公司业绩目标、制度执行、对下要管人、对外要服务顾客,总是忙了这边、忘了那边,最后吃力不讨好,还没有自己做销售时畅快 销售精英说: 我也想帮下我们店长,可除了卖卖货,也不知如何协助他,同时我自己也想有一天成长…

    2022年6月17日
    600
  • 好用的直播软件有哪些,2020直播软件排行榜

    因为新型肺炎的疫情,中小学要推迟开学,大家也都在寻找一些直播的方案,现在我将我知道的直播方案列一下,供大家参考选择。 一、QQ群视频 这是大家最熟悉的直播模式,建立班级群后,开启视频,可以播放影片、分享屏幕,也可以播放PPT课件,也有白板模式。大家可以将课件习题发放到群里让学生预习,然后通过群视频集中讲解。学生可以在电脑或手机中参与课堂。 二、希沃云课堂 安装希沃白板后,导入PPT课件,就可以开启…

    2022年6月30日
    620
  • 发布小程序需要什么,个人小程序发布流程

    什么是小程序?小程序和APP比较,有什么优势?如果这些您都还不懂,那么本文可能真的就不适合您了,多多百度一下吧。 本文将完整记录从零到小程序上线的全部过程,商家朋友也可以通过本文少走弯路,快速搭建一个属于自己的小程序,建议新手朋友收藏! 一.准备工作: 01.申请一个小程序帐号 如果有已经认证的微信公众号(服务号),那么恭喜你,你可以一分钱不花,申请一个小程序帐号,如果没有已经认证的服务号,那么,…

    2022年8月14日
    490
  • 微信如何加更多好友,微信加人小妙招分享

    分享两个100%在一周内添加5000微信好友的方法。 方法其实有很多,我今天只分享两个,一个线上用的方法,一个是线下用的方法。 首先说线上的方法:你去本地各大租房网,中介网,58同城,本地贴吧论坛,各大分类信息网,发布消息去求购,随便什么东西都可以,说你需要买什么什么东西。不出一天,会有几百个商家来加你。 方法很简单吧,因为之前有个学员开了个实体店,三个月了,一点人气都没有,月月亏损,我说你这第一…

    2022年7月2日
    480
  • 美国文化特点,美国独特的三个风俗文化分享

    美国是高度发达的资本主义超级大国,其政治、经济、军事、文化、创新等实力领衔全球。作为超级军事大国,其高等教育水平和科研技术水平也是当之无愧的世界第一,其科研经费投入之大、研究型高校企业之多、科研成果之丰富堪称世界典范。虽然当前面临各种国内外问题,美国还是因其较为健全的法律制度、健康的生活环境、顶尖的教育资源等,继续吸引着世界各地的人来这里追逐美国梦。那么美国文化的三大象征,你知道哪些呢? 接下来三…

    2022年9月30日
    3990
  • u盘有了写保护怎么解除,两种方法总有一种适合你

    U盘大家都不陌生,现在很多朋友都是使用它来存储资料。有时候怕U盘感染到病毒就会开启U盘写保护状态,有开启就会有关闭。今天,我就给大家聊一聊解除U盘写保护状态的方法 方法一、 1、双击我的电脑,右击u盘盘符,选择属性 2、选择上方的硬件一栏,点击属性 3、点击“策略” 4、将删除策略改为“更好的性能”,win7系统则是“为提高性能而优化” 方法二、上述方法只能为应急所用,想要治本还得执行以下步骤 1…

    2022年9月20日
    540
  • 企业微信申请流程(个人申请企业微信的方法)

    DoNews11月4日消息(记者刘莹)4日,企业微信对外发布了1.3版本,此次更新新增两大亮点:一是支持成员添加微信和手机通讯录中的工作伙伴为企业微信联系人;二是微信中的聊天记录和订阅文章,可一键快速转发到企业微信,企业微信中的信息也能转发到微信。 据悉,除了以上两大更新外,新版企业微信还有三个主要更新。 一是提供丰富的API接口,方便企业开发和接入更多个性化的办公应用。管理后台也为管理员提供了通…

    2022年8月17日
    860

发表回复

登录后才能评论

联系我们

400-800-8888

在线咨询: QQ交谈

邮件:admin@example.com

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

关注微信