首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设一个整形一维数组里有n(n>1)个整数,在这些整数中可以有正数也可以有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。设计一个在时间和空间两方面尽可能高效的算法,输出所有子数组的和的最大值。例如一维数组中的整数为1,-2,3,10,
设一个整形一维数组里有n(n>1)个整数,在这些整数中可以有正数也可以有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。设计一个在时间和空间两方面尽可能高效的算法,输出所有子数组的和的最大值。例如一维数组中的整数为1,-2,3,10,
admin
2017-11-20
35
问题
设一个整形一维数组里有n(n>1)个整数,在这些整数中可以有正数也可以有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。设计一个在时间和空间两方面尽可能高效的算法,输出所有子数组的和的最大值。例如一维数组中的整数为1,-2,3,10,-4,7,2,-5,则和最大的子数组为3,10,-4,7,2,该子数组的和为18。要求:
给出算法的基本设计思想。
选项
答案
算法的策略是遍历数组,用事先定义好的求和变量(初始化为0)加上当前元素后得到一个新的和,先判断这个和是否比前面已经记录的最大字数组和大,如果大,则更新此记录。然后再判断这个和是否为负数,如果是个负数,那么这个和应该被重新置0,否则这个负数将会减少接下来的和。
解析
转载请注明原文地址:https://kaotiyun.com/show/vNRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
永嘉之乱后,北方的政局是()。①西晋短暂统一的终结②北方长期处于多个政权分立的战乱状态③氐族人建立的前秦和鲜卑人建立的北魏曾统一过北方④民族交往和民族斗争交织在一起⑤民族大融合是历史发展的主流⑥民族大
1956年,苏共二十大后,匈牙利大党员和群众强烈要求克服个人崇拜,扩大民主,实行经济改革,一些由知识分子、大学生和干部组成的社团组织纷纷成立,其中最有影响者是()。
以下关于阿兹特克文化的叙述,不正确的是()。
光绪元年七月,清政府迫于()强烈要求派一位使臣到其国,()成为中国第一个驻外公使
关于德意志宗教改革的说法不正确的是()
埃及曾两次被波斯帝国征服,波斯第二次征服埃及的时间是()。
下列城市:①南京②厦门③天津④杭州,按其在近代历史上开放为商埠的时间先后顺序排列应该是()
法国里昂工人起义提出:“我们只有一个口号‘人人自由平等!’”英国宪章运动请愿书提出:“我们竭尽自由人的义务,就应享受自由人的权利。我们要求普遍选举。”这些要求表明()。①带有空想社会主义色彩②当时工人的要求还没有超出资产阶级民主主义的范畴
在周初分封中,分封同姓诸侯国、异姓诸侯国,也分封圣王之后,下面属于圣王之后的封国为()。
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
随机试题
Thetruthisbecoming______(increase)apparent.
A.藿香正气散B.不换金正气散C.葛根芩连汤D.白头翁汤E.芍药汤患者泄泻腹痛,泻下急迫,粪色黄褐,气味臭秽,肛门灼热,烦热口渴,舌质红,苔黄腻,脉滑数。治疗应首选()
高性能混凝土宜选用标准稠度用水量()的硅酸盐水泥、复合硅酸盐水泥。
社区工作的具体目标有()。
研究性学习
马某在公交车上盗窃财物,窃得一女士提包,打开一看,里面没有钱,却有手枪一把,马某随后把此枪藏于家中。对此,下列说法正确的是()。
IntheUS,aperson’scompanybuyshimorherhealthinsurance.AllemployeesintheUShavethesamekindofhealthinsurance.
A、Morethan1,000peopletookpartinthestudy.B、Peoplewhosleptlesshadhigherbloodlevelsofghrelin.C、Peoplewhoslept
Itwaseleveno’clockthatnightwhenMr.PontellierreturnedfromKlein’shotel.Hewasinanexcellenthumor,inhighspirits,
JustTooLoudTedRueterisn’tjokingaboutpossiblymovingtoNewZealand.Andifhedoesgo,itwon’tbetherageorthee
最新回复
(
0
)