【刷算法】連續子數組的最大和

ernest.wang 發布于2019-08-23 10:28 / 2809人閱讀

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云服務器云服務器最大連續子串算法算法最大子數列最大公共子串算法最大公共子圖算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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