JavaScript趣題：求解最大子數組之和

這是一個整數數組[1,-1,2]，它有如下的子數組：

1.[1] sum=>1

2.[1,-1] sum=>0

3 .[1,-1,2] sum=>2

4.[-1] sum=>-1

5.[-1,2] sum=>1

6.[2] sum=> 2

大家可以看到，這些子數組中，各元素總和最大是2。

那麼給定任意一個整數數組，怎樣求它的最大子數組之和呢？

如果仔細觀察我上面列出子數組的順序，大家可以看出這是從第一位開始窮舉。

嗯，我的方法正是窮舉，其執行的過程正是如上所示。

窮舉法在這個問題實現的效率其實並不低，可以勝任一般的需求。

我從第一個元素開始，需要遍歷N個元素。

第二個元素開始，需要遍歷N-1個元素。

......

最後一個元素開始就只有它自己，1個元素。

也就是說，窮舉法的實際複雜度是N²/2，這樣的效率還是不錯的。

function maxContiguousSum (arr) {  
    var max = 0;  
    for(var i=0;i<arr.length;i++){  
        var temp = 0;  
        for(var j=i;j<arr.length;j++){  
            temp += arr[j];  
            if(temp > max){  
                max = temp;  
            }  
        }  
    }  
    return max;  
}

以上就是 JavaScript趣題：求解最大子數組總和的內容，更多相關內容請關注PHP中文網（www.php.cn）！