資訊專欄INFORMATION COLUMN
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;
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/96372.html
摘要：給定一個整數(shù)數(shù)組，找到一個具有最大和的連續(xù)子數(shù)組子數(shù)組最少包含一個元素，返回其最大和。示例輸入輸出解釋連續(xù)子數(shù)組的和最大，為。 給定一個整數(shù)數(shù)組 nums ，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。 示例: 輸入: [-2,1,-3,4,-1,2,1,-5,4], 輸出: 6 解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。 /** * ...
摘要：如果不存在符合條件的連續(xù)子數(shù)組，返回。示例輸入輸出解釋子數(shù)組是該條件下的長度最小的連續(xù)子數(shù)組。截取從索引到索引的數(shù)組，該數(shù)組之和若小于，則繼續(xù)后移，直到大于等于。記錄與差值返回的目標數(shù)。之后后移一位繼續(xù)刷新新數(shù)組。 算法是一個程序的靈魂 公眾號：愛寫bug（ID：icodebugs）作者：愛寫bug 給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) s ，找出該數(shù)組中滿足其和 ≥ s 的...
摘要：如果不存在符合條件的連續(xù)子數(shù)組，返回。示例輸入輸出解釋子數(shù)組是該條件下的長度最小的連續(xù)子數(shù)組。截取從索引到索引的數(shù)組，該數(shù)組之和若小于，則繼續(xù)后移，直到大于等于。記錄與差值返回的目標數(shù)。之后后移一位繼續(xù)刷新新數(shù)組。 算法是一個程序的靈魂 公眾號：愛寫bug（ID：icodebugs）作者：愛寫bug 給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) s ，找出該數(shù)組中滿足其和 ≥ s 的...
摘要：動態(tài)規(guī)劃法用表示最大子數(shù)組的結(jié)束下標為的情形，則對于，有這樣就有了一個子結(jié)構(gòu)，對于初始情形，遍歷就能得到這個數(shù)組，其最大者即可最大子數(shù)組的和。動態(tài)規(guī)劃法想法巧妙，運行效率也高，但是沒有普遍的適用性。 問題簡介 ??本文將介紹計算機算法中的經(jīng)典問題——最大子數(shù)組問題（maximum subarray problem）。所謂的最大子數(shù)組問題，指的是：給定一個數(shù)組A，尋找A的和最大的非空連續(xù)...
閱讀 454·2024-11-07 18:25
閱讀 130763·2024-02-01 10:43
閱讀 944·2024-01-31 14:58
閱讀 905·2024-01-31 14:54
閱讀 83007·2024-01-29 17:11
閱讀 3265·2024-01-25 14:55
閱讀 2059·2023-06-02 13:36
閱讀 3167·2023-05-23 10:26
