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

ernest.wang 发布于2019-08-23 10:28 / 2792人阅读

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;
}

云服务器 GPU云服务器最大连续子串算法算法最大子数列最大公共子串算法最大公共子图算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/96372.html

【刷算法】LeetCode.53-最大子序和

摘要：给定一个整数数组，找到一个具有最大和的连续子数组子数组最少包含一个元素，返回其最大和。示例输入输出解释连续子数组的和最大，为。给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 /** * ...

CNZPH 2019-08-23 14:07 评论0 收藏0
LeetCode 209：最小长度的子数组 Minimum Size Subarray Sum

摘要：如果不存在符合条件的连续子数组，返回。示例输入输出解释子数组是该条件下的长度最小的连续子数组。截取从索引到索引的数组，该数组之和若小于，则继续后移，直到大于等于。记录与差值返回的目标数。之后后移一位继续刷新新数组。算法是一个程序的灵魂公众号：爱写bug（ID：icodebugs）作者：爱写bug 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的...

wow_worktile 2019-08-16 18:28 评论0 收藏0
LeetCode 209：最小长度的子数组 Minimum Size Subarray Sum

摘要：如果不存在符合条件的连续子数组，返回。示例输入输出解释子数组是该条件下的长度最小的连续子数组。截取从索引到索引的数组，该数组之和若小于，则继续后移，直到大于等于。记录与差值返回的目标数。之后后移一位继续刷新新数组。算法是一个程序的灵魂公众号：爱写bug（ID：icodebugs）作者：爱写bug 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的...

Vixb 2019-07-31 11:25 评论0 收藏0
动态规划法（八）最大子数组问题（maximum subarray problem）

摘要：动态规划法用表示最大子数组的结束下标为的情形，则对于，有这样就有了一个子结构，对于初始情形，遍历就能得到这个数组，其最大者即可最大子数组的和。动态规划法想法巧妙，运行效率也高，但是没有普遍的适用性。问题简介本文将介绍计算机算法中的经典问题——最大子数组问题（maximum subarray problem）。所谓的最大子数组问题，指的是：给定一个数组A，寻找A的和最大的非空连续...

jzman 2019-07-30 16:46 评论0 收藏0