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

admin2017-04-28 62

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

简述斯巴达克起义的原因、大体经过、意义和失败原因。

光绪元年七月，清政府迫于()强烈要求派一位使臣到其国，()成为中国第一个驻外公使

二战以来，资本主义经济在发展中出现了许多新问题，这主要表现在()

中古时代实行索贡巡行赋税征收方式的国家是()。

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

1946年3月5日，英国前首相丘吉尔在富尔敦发表了()，发出第一个明白无误的“冷战”信号。

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。

某定点机字长8位(含1位符号位)，现该机中一个寄存器的内容为43H，则将其算术左移一位、算术右移一位的结果分别为()。

某系统有R1、R2和R3共3种资源，在TO时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况如表4-4所示，此时系统的可用资源向量为(2，1，2)。试问：将系统中各种资源总数和此刻各进程对各资源的需求个数用向量或矩阵表示出来。

生活污水成分的重要特征是含有

外国企业在本国境内未设立机构、场所而取得的来源于本国境内的股息、利息、租金、特许权使用费和其他所得征收的所得税通称为()。

公民是法律概念，人民是政治概念；公民是个体概念，人民是整体概念；公民作为自然人在不同时期有不同的对象，人民作为原则是个稳定的政治概念。()

如果对旅客损害完全是由旅客自身的健康状况造成的，承运人可以不承担赔偿责任。()

科尔伯格编制了九则道德价值上互有冲突，难辨是非的故事，让被试做出判断，并说明理由，这种研究方法是。

当今世界上除了英国外，还有比利时、西班牙、加拿大、澳大利亚等国都采用君主立宪制这种政体，要想了解这种政体的情况，可供参考的文献是()。

班里有6个男生4个女生，现以随机抽签的方式选取3人去开会，则抽中1名男生、2名女生的概率在以下哪个范围之内?

ManynewcomerstotheUnitedStatesfindthemselvesstrangetotheAmericanways.Itusuallytakessometimeforthemtogetto

下列关于WindowsServer2003系统下DNS服务器配置和测试的描述中，错误的是______。

EventhoughformidablewintersarethenormintheDakotas,manypeoplewereunpreparedforthe________oftheblizzardof1888

计算机408

学硕统考专业

简述斯巴达克起义的原因、大体经过、意义和失败原因。

光绪元年七月，清政府迫于()强烈要求派一位使臣到其国，()成为中国第一个驻外公使

二战以来，资本主义经济在发展中出现了许多新问题，这主要表现在()

中古时代实行索贡巡行赋税征收方式的国家是()。

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

1946年3月5日，英国前首相丘吉尔在富尔敦发表了()，发出第一个明白无误的“冷战”信号。

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。

某定点机字长8位(含1位符号位)，现该机中一个寄存器的内容为43H，则将其算术左移一位、算术右移一位的结果分别为()。

某系统有R1、R2和R3共3种资源，在TO时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况如表4-4所示，此时系统的可用资源向量为(2，1，2)。试问：将系统中各种资源总数和此刻各进程对各资源的需求个数用向量或矩阵表示出来。

生活污水成分的重要特征是含有

外国企业在本国境内未设立机构、场所而取得的来源于本国境内的股息、利息、租金、特许权使用费和其他所得征收的所得税通称为()。

公民是法律概念，人民是政治概念；公民是个体概念，人民是整体概念；公民作为自然人在不同时期有不同的对象，人民作为原则是个稳定的政治概念。()

如果对旅客损害完全是由旅客自身的健康状况造成的，承运人可以不承担赔偿责任。()

科尔伯格编制了九则道德价值上互有冲突，难辨是非的______故事，让被试做出判断，并说明理由，这种研究方法是______。

当今世界上除了英国外，还有比利时、西班牙、加拿大、澳大利亚等国都采用君主立宪制这种政体，要想了解这种政体的情况，可供参考的文献是()。

班里有6个男生4个女生，现以随机抽签的方式选取3人去开会，则抽中1名男生、2名女生的概率在以下哪个范围之内?

ManynewcomerstotheUnitedStatesfindthemselvesstrangetotheAmericanways.Itusuallytakessometimeforthemtogetto

下列关于WindowsServer2003系统下DNS服务器配置和测试的描述中，错误的是______。

EventhoughformidablewintersarethenormintheDakotas,manypeoplewereunpreparedforthe________oftheblizzardof1888

科尔伯格编制了九则道德价值上互有冲突，难辨是非的故事，让被试做出判断，并说明理由，这种研究方法是。