Question JavaScript amusante : trouver la somme maximale des sous-tableaux

Il s'agit d'un tableau d'entiers [1,-1,2], qui contient les sous-tableaux suivants :

1.[1] sum=>1

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

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

4.[-1] somme=>-1

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

6.[2] sum=>2

Comme vous pouvez le voir, dans ces sous-tableaux, chacun La somme maximale des éléments est de 2.

Alors, étant donné n'importe quel tableau d'entiers, comment trouver la somme de ses plus grands sous-tableaux ?

Si vous regardez attentivement l'ordre dans lequel j'ai répertorié les sous-tableaux ci-dessus, vous pouvez voir que celui-ci est exhaustif à partir du premier.

Eh bien, ma méthode est exhaustive et le processus d'exécution est exactement comme indiqué ci-dessus.

L'efficacité de la méthode exhaustive pour résoudre ce problème n'est en fait pas faible et elle peut répondre aux besoins généraux.

Je pars du premier élément et je dois parcourir N éléments.

À partir du deuxième élément, N-1 éléments doivent être parcourus.

......

Le dernier élément commence par lui-même seulement, 1 élément.

En d'autres termes, la complexité réelle de la méthode exhaustive est N²/2, ce qui est assez efficace.

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

Ce qui précède est la question JavaScript amusante : trouver la somme du plus grand sous-tableau. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois (www.php.cn) !