首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设一个整形一维数组里有n(n>1)个整数,在这些整数中可以有正数也可以有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。设计一个在时间和空间两方面尽可能高效的算法,输出所有子数组的和的最大值。例如一维数组中的整数为1,—2,3,10,
设一个整形一维数组里有n(n>1)个整数,在这些整数中可以有正数也可以有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。设计一个在时间和空间两方面尽可能高效的算法,输出所有子数组的和的最大值。例如一维数组中的整数为1,—2,3,10,
admin
2017-04-28
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/tWRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
上海机器织布局
中共十四届六中全会《关于加强社会主义精神文明建设若干重要问题的决议》,强调要()。
中国共产党制定的抗日民族统一战线策略总方针的中心环节是()。
新石器时代的房屋建筑根据环境的不同形成了不同的类型,()地区多为干栏式建筑。
1543年,发表了解剖学专著《人体结构》的是()。
火的使用,是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。
1141年,金与南宋双方签订协议,规定以淮水和大散关为宋金的分界线,此协议称为()。
一个字节多路通道连接D1、D2、D3、D4、D5共5台设备,这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求,请回答下列问题:(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字
某计算机字长为16位,主存地址空间大小为128KB,按字编址。采用单字长指令格式,指令各字段定义如图B-4所示。转移指令采用相对寻址方式,相对偏移量用补码表示,寻址方式定义见表B-1。请回答下列问题:若操作码0010B表示加法操作(助记符为ad
当系统发生抖动(thrashing)时,可以采取的有效措施是____。I.撤销部分进程Ⅱ.增加磁盘交换区的容量Ⅲ.提高用户进程的优先级
随机试题
A.高位结扎及剥脱术B.旁路转流术C.切开取栓术D.全皮下切除植皮术血栓闭塞性脉管炎的治疗
膝关节化脓性关节炎病人体检时最可能发现的阳性体征是
肺癌又称为
A、由具有初级技术职务任职资格的药学、临床医学、医院感染管理和医疗行政管理等方面的专家组成B、由具有初级以上技术职务任职资格的药学、临床医学、医院感染管理和医疗行政管理等方面的专家组成C、由具有高级技术职务任职资格的药学、临床医学
男性,30岁,2个月来感右下肢无力,左下半身麻木。查体:左侧乳头水平以下痛觉和温度觉减退,右下肢腱反射亢进,右侧Babinski征阳性,右侧髂前上棘以下音叉震动觉减退,右足趾位置觉减退为明确病因,辅助检查首选
高血压伴有低血钾,应首先考虑()
下列属于基金市场服务机构的是()。①基金份额登记机构②基金销售机构③基金估值核算机构④基金投资顾问机构⑤会计师事务所⑥基金评价机构
以劳动关系的协议为主,关注的问题主要包括工作规则的建立、职业晋升阶梯和职业生涯设计、以资历为基础的报酬体系、雇佣关系和绩效评估等,属于人力资源的()。
二丑艺术浙东的有一处的戏班中,有一种脚色叫作“二花脸”,译得雅一点,那么,“二丑”就是。他和小丑的不同,不是扮横行无忌的花花公子,也不扮一味仗势的宰相家丁,他所扮演的是保护公子的拳师,或是趋奉公子的清客。总之:身份比小丑高,而性格却比小丑坏。义仆是老生扮
求下列不定积分:
最新回复
(
0
)