文档章节

求数组的最大连续子数组和

o
 osc_z1hvg4cu
发布于 2018/04/24 20:42
字数 234
阅读 8
收藏 0

精选30+云产品,助力企业轻松上云!>>>

要达到时间复杂度为n,可以采用贪心算法和动态规划。

贪心算法:

function max(arr){
    let max = arr[0],cur = 0; 
    for(let i = 0; i < arr.length; i++){
        if(cur < 0){ // 当cur < 0时,那么只要加上一个负数都会使得下一个数变小,所以可以直接弃掉,从当前i开始重新积累
            cur = arr[i];
        }else{
            cur += arr[i];
        }
        if(cur >= max){
            max = cur;
        }
    }
    return max;
}

动态规划:

 1 function max_2(arr){
 2     let max = [],result = 0;
 3     max[0] = 0;
 4     for(let i = 0; i < arr.length; i++){
 5         if(max[i] < 0){
 6             max[i+1] = arr[i];
 7         }else{
 8             max[i+1] = max[i] + arr[i];
 9         }
10         if(max[i+1] > result){
11             result = max[i+1];
12         }
13     }
14     return result;
15 }

其实这到题的动态规划的思路和贪心很像,max[i + 1]存放的就是每一次走到 i 时,cur的值。相较而言,贪心算法的空间复杂度更低,也更优。

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

JIT的Profile神器JITWatch

点击上方的蓝字关注我吧 程序那些事 简介 老是使用命令行工具在现代化社会好像已经跟不上节奏了,尤其是在做JIT分析时,使用LogCompilation输出的日志实在是太大了,让人望而生畏。有没有什么...

flydean
07/04
0
0
运维基础--虚拟机的使用(一)

虚拟机的使用 开始使用Linux操作系统时,首先可能会接触到两个主要的界面:GUI和CLI,即图形界面个命令界面,而运维一般极少使用到图形界面。 一、命令提示符的格式:[root@mylab11~] # roo...

osc_9os5791s
15分钟前
15
0
以程序员的方式,尽绵薄之力

作为程序员,我们不能冲在第一线,参与病毒防疫工作,我们希望通过我们的方式,让更多的人获取到关于疫情的有用的消息,正确的消息 虽然github可能是个相对小众的平台,对于非程序员来说,可...

Jipson
01/26
17
0
Oracle 等待事件之 db file scattered read

db file scattered read 官网解释: This event signifies that the user process is reading buffers into the SGA buffer cache and is waiting for a physical I/O call to return. A db......

osc_qlj7m2h9
16分钟前
19
0
互联网+时代的畅想

封面的台风卫星照片,我认为很形象地可以看作互联网的那一波浪潮。在智能手机普及的初始阶段,还记得我们对于互联网的狂热,有人说要用互联网颠覆一切,亦有人要用互联网干一切事情,当然,这...

zd200572
2015/09/02
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部