Un sous-tableau maximal
L’entrée est un tableau de nombres, par exemple arr = [1, -2, 3, 4, -9, 6]
.
La tâche est la suivante : trouver le sous-tableau contigu de arr
avec la somme maximale des items.
Écrire la fonction getMaxSubSum(arr)
qui retournera cette somme.
Par exemple :
getMaxSubSum([-1, 2, 3, -9]) == 5 (la somme des éléments en surbrillance)
getMaxSubSum([2, -1, 2, 3, -9]) == 6
getMaxSubSum([-1, 2, 3, -9, 11]) == 11
getMaxSubSum([-2, -1, 1, 2]) == 3
getMaxSubSum([100, -9, 2, -3, 5]) == 100
getMaxSubSum([1, 2, 3]) == 6 (prend tout)
Si tous les éléments sont négatifs, cela signifie que nous n’en prenons aucun (le sous-tableau est vide), la somme est donc zéro :
getMaxSubSum([-1, -2, -3]) = 0
S’il vous plaît essayez de penser à une solution rapide : O(n2) ou même à O(n) si vous le pouvez.
Solution lente
Nous pouvons calculer tous les subsums possibles.
Le moyen le plus simple consiste à prendre chaque élément et à calculer les sommes de tous les sous-tableaux à partir de celui-ci.
Par exemple, pour [-1, 2, 3, -9, 11]
:
// Commence à -1 :
-1
-1 + 2
-1 + 2 + 3
-1 + 2 + 3 + (-9)
-1 + 2 + 3 + (-9) + 11
// Commence à 2 :
2
2 + 3
2 + 3 + (-9)
2 + 3 + (-9) + 11
// Commence à 3 :
3
3 + (-9)
3 + (-9) + 11
// Commence à -9 :
-9
-9 + 11
// Commence à 11 :
11
Le code est en réalité une boucle imbriquée : la boucle externe recouvrant les éléments du tableau, et l’interne compte les sous-sommes commençant par l’élément en cours.
function getMaxSubSum(arr) {
let maxSum = 0; // si on ne prend aucun élément, zéro sera retourné
for (let i = 0; i < arr.length; i++) {
let sumFixedStart = 0;
for (let j = i; j < arr.length; j++) {
sumFixedStart += arr[j];
maxSum = Math.max(maxSum, sumFixedStart);
}
}
return maxSum;
}
alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100
La solution a une complexité temporelle de O(n2). En d’autres termes, si nous augmentons la taille du tableau 2 fois, l’algorithme fonctionnera 4 fois plus longtemps.
Pour les grands tableaux (1’000, 10’000 éléments ou plus), de tels algorithmes peuvent conduire à une grande lenteur.
Solution rapide
Parcourons le tableau et conservons la somme partielle actuelle des éléments dans la variable s
. Si s
devient négatif à un moment donné, assignez s=0
. Le maximum de tous ces s
sera la réponse.
Si la description est trop vague, veuillez voir le code, il est assez court :
function getMaxSubSum(arr) {
let maxSum = 0;
let partialSum = 0;
for (let item of arr) { // pour chaque élément d'arr
partialSum += item; // l'ajouter à partialSum
maxSum = Math.max(maxSum, partialSum); // mémorise le maximum
if (partialSum < 0) partialSum = 0; // zéro si négatif
}
return maxSum;
}
alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([-1, -2, -3]) ); // 0
L’algorithme nécessite exactement 1 passage de tableau, la complexité temporelle est donc O(n).
Vous pouvez trouver plus d’informations détaillées sur l’algorithme ici : Maximum subarray problem. Si la raison de ce fonctionnement n’est pas encore évidente, tracez l’algorithme à partir des exemples ci-dessus et voyez comment il fonctionne.