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(n²) ou même à O(n) si vous le pouvez.

Open a sandbox with tests.

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(n²). 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.

Ouvrez la solution avec des tests dans une sandbox.