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

admin2017-11-20 32

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

中国第一个资产阶级革命团体兴中会建立的时间是()。

下列关于古日耳曼人的社会状况的叙述中，不正确的是()。

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

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

下列关于湘军的叙述中不正确的是()。

近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。

在1875年宪法中关于法国立法权的叙述，不正确的是()。

文艺复兴运动兴起的时间是()。

在周初分封中，分封同姓诸侯国、异姓诸侯国，也分封圣王之后，下面属于圣王之后的封国为()。

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

股骨下1/3骨折病人行骨牵引治疗时将膝关节放在屈曲位的目的是（）

Nelson综合征表现为库欣综合症表现为

心源性呼吸困难的表现，不包括()。

下列属于所有权的原始取得方法的有：

若BEP(％)表示某项目的盈亏平衡点设计生产能力利用率，则下列方案中抗风险能力最强的是()。

根据我国现行规定，土地增值税实行()。

与利润最大化目标相比，以每股收益最大化作为企业财务管理的目标，其优点在于()。

根据资源税有关规定，下列说法符合资源税纳税地点规定的是()。

下列关于BGP协议的描述中，错误的是()。