【刷算法】连续子数组的最大和

简介: 【刷算法】连续子数组的最大和

题目描述


HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组,返回它的最大连续子序列的和,你会不会被他忽悠住?(子向量的长度至少是1)


分析


首先如果数组里面全是小于0的负数,那么连续数组的最大和就是那个最大的负数

如果里面有正数还有负数,那么从左开始累加,如果遇到累加和小于0,则说明这一段数组不会是构成最大和的连续子数组,道理很简单,如果构成最大和的连续子数组中包含这么一段累加和为负数的子数组,那么去掉它们之后和不就更大了么?所以不会包含。

需要两个变量max和cur,cur记录当前的累积和,小于0立马开始从0计算,max记录遍历过程中出现过的累积和中的最大值。


代码实现


function FindGreatestSumOfSubArray(arr)
{
    if(arr.length === 0)
        return;
    if(arr.length === 1)
        return arr[0];
    var allNeg = true;
    var negMax = -Infinity;
    for(var i = 0;i < arr.length;i++) {
        if(arr[i] > negMax){
            negMax = arr[i];
        }
        if(arr[i] >= 0){
            allNeg = false;
        }
    }
    if(allNeg)
        return negMax;
    var max = -Infinity, cur = 0;
    for(var i = 0;i < arr.length;i++) {
        cur += arr[i];
        max = Math.max(max, cur);
        cur = cur >=0 ? cur : 0;
    }
    return max;
}



相关文章
create-react-app配置环境变量
create-react-app配置环境变量
240 0
|
网络协议 网络安全 Python
Python 通过UDP传输超过64k的信息
Python 通过UDP传输超过64k的信息 原创
228 0
|
数据可视化 Python
Python蒙特卡罗(Monte Carlo)模拟计算投资组合的风险价值(VaR)
Python蒙特卡罗(Monte Carlo)模拟计算投资组合的风险价值(VaR)
|
Web App开发 前端开发 容器
|
JavaScript 前端开发
迷失中的this指向,看完这篇就会了
this是一个比较迷惑人的东西,尽管你对this有很多的了解,但是面试题里面考察this指向,总会让你有种猜谜的感觉,知道一些,但是还是会出错,或许你猜对了,但是又好像解释不太清楚。
132 0
迷失中的this指向,看完这篇就会了
|
JavaScript Java API
TypeScript 中「泛型」的基本使用
TypeScript 中「泛型」的基本使用
144 0
|
架构师 程序员
研发职位到底应该怎么设置?(上)
研发职位到底应该怎么设置?(上)
247 0
研发职位到底应该怎么设置?(上)
成功解决TypeError: a bytes-like object is required, not 'str'
成功解决TypeError: a bytes-like object is required, not 'str'
|
算法 5G 调度
开环空间复用 | 带你读《大规模天线波束赋形技术原理与设计 》之四
所谓开环空间复用, 是指预编码的计算不取决于信道状态信息的反馈。
开环空间复用  | 带你读《大规模天线波束赋形技术原理与设计 》之四
|
存储 固态存储 大数据
大数据存储平台之异构存储实践
经常做数据处理的伙伴们肯定会有这样一种体会:最近一周内的数据会被经常使用到,而比如最近几周的数据使用率会有下降,每周仅仅被访问几次;在比如3月以前的数据使用率会大幅下滑,存储的数据可能一个月才被访问几次。
14790 0