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

admin2017-11-20 39

问题设一个整形一维数组里有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月，发表《立宪法议》，首先提出君主立宪要求的是()。

以下关于阿兹特克文化的叙述，不正确的是()。

关于德意志宗教改革的说法不正确的是()

“我不想变成上帝，或居住在永恒之中，或者把天地抱在怀里，属于人的那种光荣对我就够了。我自己是凡人，我只要求凡人的幸福。”这句话体现的思想是()

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

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

1922年2月，美、英、法、意、日五国通过了《五国海军条约》，规定了各国海军主力舰和航空母舰的限额，以及在东亚设置海军基地的要求等内容。该条约的缔结表明()

绘制网络图的规则与方法。

关于皮肤针，下列说法不正确的是

收益性物业可以获取的最大租金收入称为有效毛收入。()[2009年考题]

下列有关房地产抵押的表述中，不正确的是()。[2003年考题]

商业银行存放在中央银行的一般性存款的作用之一是用来满足结算的需求，另一作用是()。

下图为某地区地理信息系统数据库示意图。谚语《九九歌》中“一九二九不出手，三九四九冰上走，五九六九河边看柳，七九河开，八九雁来，九九加一九，耕牛遍地走”所述地区()。

下列关于人民警察身份保障权利的表述，正确的是()。

设有定义：intsum=100，i；以下选项中，能够实现sum-=1+2+3…+10的程序段是()。