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 個の要素をトラバースする必要があります。

2 番目の要素から始めて、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 中国語 Web サイト (www.php.cn) に注目してください。