设一个整形一维数组里有n(n＞1)个整数，在这些整数中可以有正数也可以有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。设计一个在时间和空间两方面尽可能高效的算法，输出所有子数组的和的最大值。例如一维数组中的整数为1，-2，3，10，

admin2017-11-20 63

问题设一个整形一维数组里有n(n＞1)个整数，在这些整数中可以有正数也可以有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。设计一个在时间和空间两方面尽可能高效的算法，输出所有子数组的和的最大值。例如一维数组中的整数为1，-2，3，10，-4，7，2，-5，则和最大的子数组为3，10，-4，7，2，该子数组的和为18。要求：
说明所设计算法的时间复杂度和空间复杂度。

选项

答案时间复杂分析：整个算法过程相当于把数组遍历了一遍，所以时间复杂度为O(n)。空间复杂度分析：算法中只需要使用sum和max这两个临时变量，所以空间复杂度为一常数，表示为O(1)。

解析

转载请注明原文地址:https://www.kaotiyun.com/show/cNRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

在下列我国建国之后的外交活动中，能够体现“和而不同”思想的有()①亚非会议主张“求同存异”②提出“和平共处五项原则”③中日关系实现正常化④同第三世界国家建立友谊

永嘉之乱后，北方的政局是()。①西晋短暂统一的终结②北方长期处于多个政权分立的战乱状态③氐族人建立的前秦和鲜卑人建立的北魏曾统一过北方④民族交往和民族斗争交织在一起⑤民族大融合是历史发展的主流⑥民族大

1956年，苏共二十大后，匈牙利大党员和群众强烈要求克服个人崇拜，扩大民主，实行经济改革，一些由知识分子、大学生和干部组成的社团组织纷纷成立，其中最有影响者是()。

1901年6月，发表《立宪法议》，首先提出君主立宪要求的是()。

宁夏回族自治区的设立时间是()。

第一国际成立前，各国无产阶级强烈要求加强国际团结的直接原因是()。

19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

全国高校院系调整的具体时间是()。

詹天佑自主设计修建了中国第一条铁路是在()。

全国高校院系调整的具体时间是()。

试述音高、音强、音长、音色和现代汉语语音的关系。

某男，60岁，患糖尿病6年，半年来项部近发际处，经常出现红肿块，灼热疼痛，出脓后即愈合，触之突起根浅，服用抗生素，无明显效果，常口渴唇燥，舌红苔薄，脉细数。中医诊断为

间歇脉多见于

消防应急照明和疏散指示系统管路明敷时，应在相关部位设置吊点或支点，吊杆直径不应小于6mm。其中相关部位不包括()。

信用证在汇票条款中注明“Drawnonus”，出口商缮制汇票时，应将付款人作成()。

股权投资基金管理人在基金运作中具有核心作用，基金管理人主要具有下列哪些职能()。I．基金产品的设计Ⅱ．基金份额的销售Ⅲ．基金份额的备案Ⅳ．基金资产的管理

对开展理财顾问业务而言，关于客户的重要的非财务信息是()。

自主学习的特征有()。①自立性②自为性⑧自律性

实现“从学生信息表中找出性别为女的学生姓名”的SQL语句是

WemetMaryandherhusbandatapartytwomonthsago.______we’vehadnofurthercommunication.