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

admin2017-11-20 23

问题设一个整形一维数组里有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

学硕统考专业

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

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

元朝各行政区的行政机构称为()。()有指挥军事活动的权力，遇有征伐则设置()。

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

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

下列有关《布列斯特和约》的说法中，错误的一项是()。

关于美国内战，不正确的说法是()。

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

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

A．贫血伴球形红细胞增多B．贫血伴靶形红细胞增多C．贫血伴红细胞碎片增多D．贫血伴红细胞CD55、CD59降低E．贫血伴血肌酐增高阵发性睡眠性血红蛋白尿症

A、时好时坏，病情进展缓慢B、起病急骤，进展迅速C、病情急剧，危及生命D、脏器衰退，代偿不足E、症状消除，逐渐恢复老年病人病情特点（）。

“进口口岸”栏应填()。“项号”栏应填()。

我国境内的股票价格指数不包括()。

根据《行政处罚法》的规定，下列关于行政拘留的说法正确的是()。

“几鼎既成，迁于三国。夏后氏失之，殷人受之；殷人失之，周人受之。”其中所说的“九鼎”之所以被广泛重视并在夏商周流转，主要因为它是()。

Heistooyoungtobeableto______betweenrightandwrong.

Withfuelpricesgoingup，carbuyersarechangingtheirideaofbuyingacar．