首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设一个整形一维数组里有n(n>1)个整数,在这些整数中可以有正数也可以有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。设计一个在时间和空间两方面尽可能高效的算法,输出所有子数组的和的最大值。例如一维数组中的整数为1,—2,3,10,
设一个整形一维数组里有n(n>1)个整数,在这些整数中可以有正数也可以有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。设计一个在时间和空间两方面尽可能高效的算法,输出所有子数组的和的最大值。例如一维数组中的整数为1,—2,3,10,
admin
2017-04-28
40
问题
设一个整形一维数组里有n(n>1)个整数,在这些整数中可以有正数也可以有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。设计一个在时间和空间两方面尽可能高效的算法,输出所有子数组的和的最大值。例如一维数组中的整数为1,—2,3,10,—4,7,2,—5,则和最大的子数组为3,10,—4,7,2,该子数组的和为18。要求:
说明你所设计算法的时间复杂度和空间复杂度。
选项
答案
时间复杂度分析:整个算法过程相当于把数组遍历了一遍,所以时间复杂度为O(n)。 空间复杂度分析:算法中只需要使用sum和max这两个临时变量,所以空间复杂度为一常数,表示为O(1)。
解析
转载请注明原文地址:https://jikaoti.com/ti/zIfjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
论述淝水之战的性质及双方胜负的原因。
1934年9月苏联加入国联,对此说法错误的一项是()。
文艺复兴运动兴起的时间是()。
林则徐的反英国侵略的策略思想不包括()。
建立帝国财政收支总账和元首金库,直接控制和调节全国财政收支的是()。
在击溃国民党的全面进攻和重点进攻中,人民解放军的主要作战目标是()。
以下不属于国民党控制金融的“四行”的是()。
(1)根据无类IP地址的规则,每个网段中有两个地址是不分配的:主机号全0表示网络地址,主机号全1表示广播地址。因此8位主机号所能表示的主机数就是28-2,即254台。该网络要划分为两个子网,每个子网要120台主机,因此主机位数X应该满足下面三个条件:
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态,且进程A先得到CPU运行,进程B后运行。进程A的运行轨迹为:计算50ms,打印信息100ms,再计算50ms,打印信息100ms,结束。进程B的运行轨迹为:计算50
设某计算机有四级中断A、B、C、D,其硬件排队优先级次序为A>B>C>D。下表列出了执行每级中断服务程序所需的时间。如果以执行中断服务程序的时间作为确定中断优先级的尺度:时间越短优先级越高。(1)请指出如何为各级中断服务程序设置屏蔽码?
随机试题
苏式面点的成熟方法以蒸、煮、烤为主。()
A.咽痛伴发热2天B.咽痛伴张口受限2天C.咽痛伴饮水呛咳,讲话含混不清2天D.咽痛伴咳痰带血丝2月E.咽痛伴声嘶2天急性会厌炎最有可能的表现是
背景资料:某施工单位承接了长68km的平原区新建高速公路路面施工,路面面层采用C30水泥混凝土,基层为水泥稳定碎石,底基层为级配碎石,土路肩采用M7.5浆砌片石加固。路面结构如下图所示。施工单位采用中心站集中拌和法施工水泥稳定碎石基层
企业每月要将所有收入账户期末余额转入本年利润账户借方。()
2015年1月1日,甲公司向乙公司借款100万元,借款期限为1年(2015年1月1日至2015年12月31日),双方未约定借期内是否支付利息,也未约定逾期利率。应债权人乙公司的要求,丙公司以其小汽车为该笔借款提供了抵押担保,2015年1月1日双方签订了书面
案例:下面是某教师关于动量概念的教学。教师:前面几章我们主要应用牛顿运动定律研究了物体的运动,但对于有些物体的运动直接应用牛顿运动定律会有困难,如爆炸类物体、碰撞等,这类运动有什么特征?学生:运动非常剧烈。教师:不是指这个方面,我指的是它们运动的时
现在几乎所有的高楼大厦都安装了电梯,但管理人员明显不懂得电梯的维护知识,这些人会按照产品维修保护手册或厂家售后服务人员的提示做定期检修。但某位有经验的看电梯师傅说,每隔一年做一次定期检修,只能检查出电梯可能存在问题的一小部分,这样的检查是没有意义的,完全是
按照我国法律部门划分的标准和原则,《澳门特别行政区基本法》属于()
【背景素材】校摄影社团在今年的摄影比赛结束后,希望可以借助PowerPoint将优秀作品在社团活动中进行展示。这些优秀的摄影作品保存在考试文件夹中,并以“Photo(1).jpg”~“Photo(12).Jpg”命名。现在,请你按照如下需求
A、Takeanexam.B、Dosomereading.C、Declarehermajor.D、Haveaninterview.B推理判断题。女士在对话结尾时说期末考试前她还要看很多书,可见她挂电话是为了去看书,故选B。注意本题问
最新回复
(
0
)