Les objets vous permettent de stocker des collections de valeurs saisies. C'est très bien.
Mais bien souvent, nous constatons que nous avons besoin d’une collection ordonnée , où nous avons un 1er, un 2ème, un 3ème élément et ainsi de suite. Par exemple, nous en avons besoin pour stocker une liste de quelque chose : utilisateurs, biens, éléments HTML, etc.
Il n'est pas pratique d'utiliser un objet ici, car il ne fournit aucune méthode pour gérer l'ordre des éléments. Nous ne pouvons pas insérer une nouvelle propriété « entre » celles existantes. Les objets ne sont tout simplement pas destinés à un tel usage.
Il existe une structure de données spéciale nommée Array , pour stocker les collections ordonnées.
Il existe deux syntaxes pour créer un tableau vide :
let arr = nouveau tableau(); soit arr = [];
Presque tout le temps, la seconde syntaxe est utilisée. Nous pouvons fournir des éléments initiaux entre parenthèses :
laissez fruits = ["Pomme", "Orange", "Prune"];
Les éléments du tableau sont numérotés en commençant par zéro.
On peut obtenir un élément par son numéro entre crochets :
laissez fruits = ["Pomme", "Orange", "Prune"]; alerte( fruits[0] ); // Pomme alerte( fruits[1] ); // Orange alerte( fruits[2] ); // Prune
On peut remplacer un élément :
fruits[2] = 'Poire'; // maintenant ["Pomme", "Orange", "Poire"]
…Ou ajoutez-en un nouveau au tableau :
fruits[3] = 'Citron'; // maintenant ["Pomme", "Orange", "Poire", "Citron"]
Le nombre total d'éléments dans le tableau est sa length :
laissez fruits = ["Pomme", "Orange", "Prune"]; alert( fruits.length ); // 3
Nous pouvons également utiliser alert pour afficher l’ensemble du tableau.
laissez fruits = ["Pomme", "Orange", "Prune"]; alerte( fruits ); // Pomme, Orange, Prune
Un tableau peut stocker des éléments de n'importe quel type.
Par exemple:
// mélange de valeurs
let arr = [ 'Apple', { nom : 'John' }, true, function() { alert('hello'); } ];
// récupère l'objet à l'index 1 puis affiche son nom
alerte( arr[1].name ); // John
// récupère la fonction à l'index 3 et l'exécute
arr[3](); // BonjourVirgule finale
Un tableau, tout comme un objet, peut se terminer par une virgule :
laissez les fruits = [ "Pomme", "Orange", "Prune", ];
Le style « virgule finale » facilite l'insertion/suppression d'éléments, car toutes les lignes se ressemblent.
Un ajout récent
Il s'agit d'un ajout récent à la langue. Les anciens navigateurs peuvent avoir besoin de polyfills.
Disons que nous voulons le dernier élément du tableau.
Certains langages de programmation autorisent l'utilisation d'index négatifs dans le même but, comme fruits[-1] .
Cependant, en JavaScript, cela ne fonctionnera pas. Le résultat sera undefined , car l'index entre crochets est traité littéralement.
Nous pouvons calculer explicitement l'index du dernier élément puis y accéder : fruits[fruits.length - 1] .
laissez fruits = ["Pomme", "Orange", "Prune"]; alerte( fruits[fruits.length-1] ); // Prune
Un peu encombrant, non ? Nous devons écrire le nom de la variable deux fois.
Heureusement, il existe une syntaxe plus courte : fruits.at(-1) :
laissez fruits = ["Pomme", "Orange", "Prune"]; // identique à fruits[fruits.length-1] alerte( fruits.at(-1) ); // Prune
En d’autres termes, arr.at(i) :
est exactement la même chose que arr[i] , si i >= 0 .
pour les valeurs négatives de i , il recule par rapport à la fin du tableau.
Une file d'attente est l'une des utilisations les plus courantes d'un tableau. En informatique, cela signifie une collection ordonnée d’éléments qui prend en charge deux opérations :
push ajoute un élément à la fin.
shift récupère un élément depuis le début, en avançant la file d'attente, de sorte que le 2ème élément devienne le 1er.
Les tableaux prennent en charge les deux opérations.
En pratique, nous en avons besoin très souvent. Par exemple, une file d'attente de messages qui doivent être affichés à l'écran.
Il existe un autre cas d'utilisation des tableaux : la structure de données nommée pile.
Il prend en charge deux opérations :
push ajoute un élément à la fin.
pop prend un élément de la fin.
Ainsi, de nouveaux éléments sont ajoutés ou retirés toujours à partir de la « fin ».
Une pile est généralement illustrée comme un paquet de cartes : de nouvelles cartes sont ajoutées au sommet ou prises par le haut :
Pour les piles, le dernier élément poussé est reçu en premier, c'est également appelé principe LIFO (Last-In-First-Out). Pour les files d’attente, nous avons le FIFO (First-In-First-Out).
Les tableaux en JavaScript peuvent fonctionner à la fois comme file d'attente et comme pile. Ils vous permettent d'ajouter/supprimer des éléments, à la fois vers/depuis le début ou la fin.
En informatique, la structure de données qui permet cela est appelée deque.
Méthodes qui fonctionnent avec la fin du tableau :
pop
Extrait le dernier élément du tableau et le renvoie :
laissez fruits = ["Pomme", "Orange", "Poire"]; alerte( fruits.pop() ); // supprime "Pear" et alerte-le alerte( fruits ); // Pomme, Orange
fruits.pop() et fruits.at(-1) renvoient le dernier élément du tableau, mais fruits.pop() modifie également le tableau en le supprimant.
push
Ajoutez l'élément à la fin du tableau :
laissez fruits = ["Pomme", "Orange"];
fruits.push("Poire");
alerte( fruits ); // Pomme, Orange, Poire L'appel fruits.push(...) est égal à fruits[fruits.length] = ... .
Méthodes qui fonctionnent avec le début du tableau :
shift
Extrait le premier élément du tableau et le renvoie :
laissez fruits = ["Pomme", "Orange", "Poire"]; alert( fruits.shift() ); // supprime Apple et l'alerte alerte( fruits ); // Orange, Poire
unshift
Ajoutez l'élément au début du tableau :
laissez fruits = ["Orange", "Poire"];
fruits.unshift('Pomme');
alerte( fruits ); // Pomme, Orange, Poire Les méthodes push et unshift peuvent ajouter plusieurs éléments à la fois :
laissez fruits = ["Pomme"];
fruits.push("Orange", "Pêche");
fruits.unshift("Ananas", "Citron");
// ["Ananas", "Citron", "Pomme", "Orange", "Pêche"]
alerte( fruits ); Un tableau est un type particulier d'objet. Les crochets utilisés pour accéder à une propriété arr[0] proviennent en réalité de la syntaxe de l'objet. C'est essentiellement la même chose que obj[key] , où arr est l'objet, tandis que les nombres sont utilisés comme clés.
Ils étendent les objets en fournissant des méthodes spéciales pour travailler avec des collections ordonnées de données ainsi que la propriété length . Mais au fond, c'est toujours un objet.
N'oubliez pas qu'il n'existe que huit types de données de base en JavaScript (voir le chapitre Types de données pour plus d'informations). Le tableau est un objet et se comporte donc comme un objet.
Par exemple, il est copié par référence :
laissez fruits = ["Banane"]
soit arr = fruits ; // copie par référence (deux variables référencent le même tableau)
alerte( arr === fruits ); // vrai
arr.push("Poire"); // modifie le tableau par référence
alerte( fruits ); // Banane, Poire - 2 articles maintenant… Mais ce qui rend les tableaux vraiment spéciaux, c'est leur représentation interne. Le moteur essaie de stocker ses éléments dans la zone mémoire contiguë, l'un après l'autre, comme le montrent les illustrations de ce chapitre, et il existe également d'autres optimisations pour que les tableaux fonctionnent très rapidement.
Mais ils se cassent tous si nous arrêtons de travailler avec un tableau comme avec une « collection ordonnée » et commençons à travailler avec lui comme s'il s'agissait d'un objet normal.
Par exemple, techniquement, nous pouvons faire ceci :
laissez fruits = []; // crée un tableau fruits[99999] = 5 ; // assigne une propriété avec un index bien supérieur à sa longueur fruits.age = 25 ; // crée une propriété avec un nom arbitraire
C'est possible, car les tableaux sont des objets à leur base. Nous pouvons leur ajouter n’importe quelle propriété.
Mais le moteur verra que nous travaillons avec le tableau comme avec un objet normal. Les optimisations spécifiques aux baies ne sont pas adaptées à de tels cas et seront désactivées, leurs avantages disparaîtront.
Les façons d'abuser d'un tableau :
Ajoutez une propriété non numérique comme arr.test = 5 .
Faites des trous, comme : ajoutez arr[0] puis arr[1000] (et rien entre eux).
Remplissez le tableau dans l'ordre inverse, comme arr[1000] , arr[999] et ainsi de suite.
Veuillez considérer les tableaux comme des structures spéciales permettant de travailler avec les données ordonnées . Ils proposent des méthodes spéciales pour cela. Les tableaux sont soigneusement réglés dans les moteurs JavaScript pour fonctionner avec des données ordonnées contiguës. Veuillez les utiliser de cette façon. Et si vous avez besoin de clés arbitraires, il y a de fortes chances que vous ayez réellement besoin d'un objet régulier {} .
Les méthodes push/pop s'exécutent rapidement, tandis que shift/unshift sont lentes.
Pourquoi est-il plus rapide de travailler avec la fin d’un tableau qu’avec son début ? Voyons ce qui se passe pendant l'exécution :
fruits.shift(); // prend 1 élément depuis le début
Il ne suffit pas de prendre et de supprimer l'élément avec l'index 0 . D'autres éléments doivent également être renumérotés.
L'opération shift doit faire 3 choses :
Supprimez l'élément avec l'index 0 .
Déplacez tous les éléments vers la gauche, renumérotez-les de l'index 1 à 0 , de 2 à 1 et ainsi de suite.
Mettez à jour la propriété length .
Plus il y a d'éléments dans le tableau, plus il y a de temps pour les déplacer et plus d'opérations en mémoire.
La même chose se produit avec unshift : pour ajouter un élément au début du tableau, il faut d'abord déplacer les éléments existants vers la droite, en augmentant leurs index.
Et c'est quoi ce push/pop ? Ils n’ont rien à déplacer. Pour extraire un élément de la fin, la méthode pop nettoie l'index et raccourcit length .
Les actions pour l'opération pop :
fruits.pop(); // prend 1 élément à la fin
La méthode pop n'a pas besoin de déplacer quoi que ce soit, car les autres éléments conservent leurs index. C'est pourquoi c'est incroyablement rapide.
La même chose avec la méthode push .
L'une des méthodes les plus anciennes pour parcourir les éléments d'un tableau est la boucle for sur les index :
let arr = ["Pomme", "Orange", "Poire"];
pour (soit i = 0; i < arr.length; i++) {
alerte( arr[i] );
} Mais pour les tableaux, il existe une autre forme de boucle, for..of :
laissez fruits = ["Pomme", "Orange", "Prune"];
// parcourt les éléments du tableau
pour (que le fruit des fruits) {
alerte( fruit );
} Le for..of ne donne pas accès au numéro de l'élément courant, juste à sa valeur, mais dans la plupart des cas cela suffit. Et c'est plus court.
Techniquement, les tableaux étant des objets, il est également possible d'utiliser for..in :
let arr = ["Pomme", "Orange", "Poire"];
pour (laisser la clé dans arr) {
alerte( arr[clé] ); // Pomme, Orange, Poire
}Mais c'est en fait une mauvaise idée. Il y a des problèmes potentiels avec cela :
La boucle for..in parcourt toutes les propriétés , pas seulement les propriétés numériques.
Il existe des objets dits « de type tableau » dans le navigateur et dans d'autres environnements, qui ressemblent à des tableaux . Autrement dit, ils ont des propriétés length et d'index, mais ils peuvent également avoir d'autres propriétés et méthodes non numériques, dont nous n'avons généralement pas besoin. La boucle for..in les listera cependant. Donc, si nous devons travailler avec des objets de type tableau, alors ces propriétés « supplémentaires » peuvent devenir un problème.
La boucle for..in est optimisée pour les objets génériques, pas pour les tableaux, et est donc 10 à 100 fois plus lente. Bien sûr, cela reste très rapide. L’accélération n’a d’importance que dans les goulots d’étranglement. Mais nous devons quand même être conscients de la différence.
Généralement, nous ne devrions pas utiliser for..in pour les tableaux.
La propriété length se met automatiquement à jour lorsque nous modifions le tableau. Pour être précis, il ne s'agit pas en fait du nombre de valeurs dans le tableau, mais du plus grand index numérique plus un.
Par exemple, un seul élément avec un grand indice donne une grande longueur :
laissez fruits = []; fruits[123] = "Pomme"; alert( fruits.length ); // 124
Notez que nous n’utilisons généralement pas de tableaux comme celui-là.
Une autre chose intéressante à propos de la propriété length est qu'elle est accessible en écriture.
Si nous l'augmentons manuellement, rien d'intéressant ne se produit. Mais si on le diminue, le tableau est tronqué. Le processus est irréversible, voici l'exemple :
soit arr = [1, 2, 3, 4, 5]; arr.longueur = 2; // tronqué à 2 éléments alerte( arr ); // [1, 2] arr.longueur = 5 ; // renvoie la longueur alerte( arr[3] ); // non défini : les valeurs ne reviennent pas
Ainsi, le moyen le plus simple d'effacer le tableau est : arr.length = 0; .
Il existe une autre syntaxe pour créer un tableau :
let arr = new Array("Pomme", "Poire", "etc"); Il est rarement utilisé car les crochets [] sont plus courts. En outre, il comporte une fonctionnalité délicate.
Si new Array est appelé avec un seul argument qui est un nombre, alors il crée un tableau sans éléments, mais avec la longueur donnée .
Voyons comment on peut se tirer une balle dans le pied :
let arr = nouveau tableau (2); // va-t-il créer un tableau de [2] ? alerte( arr[0] ); // non défini ! aucun élément. alert( arr.length ); // longueur 2
Pour éviter de telles surprises, nous utilisons généralement des crochets, à moins que nous sachions vraiment ce que nous faisons.
Les tableaux peuvent contenir des éléments qui sont également des tableaux. On peut l'utiliser pour des tableaux multidimensionnels, par exemple pour stocker des matrices :
soit matrice = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]; alerte( matrice[0][1] ); // 2, la deuxième valeur du premier tableau interne
Les tableaux ont leur propre implémentation de la méthode toString qui renvoie une liste d'éléments séparés par des virgules.
Par exemple:
soit arr = [1, 2, 3]; alerte( arr ); // 1,2,3 alerte( String(arr) === '1,2,3' ); // vrai
Essayons également ceci :
alerte( [] + 1 ); // "1" alerte( [1] + 1 ); // "11" alerte( [1,2] + 1 ); // "1,21"
Les tableaux n'ont pas Symbol.toPrimitive , ni une valueOf viable, ils implémentent uniquement la conversion toString , donc ici [] devient une chaîne vide, [1] devient "1" et [1,2] devient "1,2" .
Lorsque l'opérateur binaire plus "+" ajoute quelque chose à une chaîne, il la convertit également en chaîne, donc l'étape suivante ressemble à ceci :
alerte( "" + 1 ); // "1" alerte( "1" + 1 ); // "11" alerte( "1,2" + 1 ); // "1,21"
Les tableaux en JavaScript, contrairement à certains autres langages de programmation, ne doivent pas être comparés à Operator == .
Cet opérateur n'a pas de traitement spécial pour les tableaux, il fonctionne avec eux comme avec n'importe quel objet.
Rappelons les règles :
Deux objets sont égaux == seulement s'ils font référence au même objet.
Si l'un des arguments de == est un objet et l'autre est une primitive, alors l'objet est converti en primitif, comme expliqué dans le chapitre Conversion d'objet en primitive.
… À l'exception de null et undefined qui sont égaux == l'un à l'autre et rien d'autre.
La comparaison stricte === est encore plus simple, car elle ne convertit pas les types.
Ainsi, si nous comparons des tableaux avec == , ils ne sont jamais identiques, sauf si nous comparons deux variables qui font référence exactement au même tableau.
Par exemple:
alerte( [] == [] ); // FAUX alerte( [0] == [0] ); // FAUX
Ces tableaux sont des objets techniquement différents. Ils ne sont donc pas égaux. L'opérateur == n'effectue pas de comparaison élément par élément.
La comparaison avec les primitives peut également donner des résultats apparemment étranges :
alerte( 0 == [] ); // vrai
alerte('0' == [] ); // FAUX Ici, dans les deux cas, nous comparons une primitive avec un objet tableau. Ainsi, le tableau [] est converti en primitif à des fins de comparaison et devient une chaîne vide '' .
Ensuite, le processus de comparaison continue avec les primitives, comme décrit dans le chapitre Conversions de types :
// après que [] ait été converti en ''
alerte( 0 == '' ); // vrai, car '' est converti en numéro 0
alerte('0' == '' ); // faux, pas de conversion de type, chaînes différentesAlors, comment comparer les tableaux ?
C'est simple : n'utilisez pas l'opérateur == . Au lieu de cela, comparez-les élément par élément dans une boucle ou en utilisant les méthodes d'itération expliquées dans le chapitre suivant.
Un tableau est un type particulier d'objet, adapté au stockage et à la gestion d'éléments de données ordonnés.
La déclaration :
// crochets (habituel) let arr = [élément1, élément2...]; // nouveau tableau (exceptionnellement rare) let arr = nouveau tableau (élément1, élément2...);
L'appel à new Array(number) crée un tableau avec la longueur donnée, mais sans éléments.
La propriété length est la longueur du tableau ou, pour être précis, son dernier index numérique plus un. Il est automatiquement ajusté par des méthodes de tableau.
Si nous raccourcissons manuellement length , le tableau est tronqué.
Récupération des éléments :
nous pouvons obtenir un élément par son index, comme arr[0]
nous pouvons également utiliser la méthode at(i) qui autorise les index négatifs. Pour les valeurs négatives de i , il recule par rapport à la fin du tableau. Si i >= 0 , cela fonctionne de la même manière que arr[i] .
Nous pouvons utiliser un tableau comme deque avec les opérations suivantes :
push(...items) ajoute items à la fin.
pop() supprime l'élément de la fin et le renvoie.
shift() supprime l'élément du début et le renvoie.
unshift(...items) ajoute items au début.
Pour parcourir les éléments du tableau :
for (let i=0; i<arr.length; i++) – fonctionne le plus rapidement et est compatible avec les anciens navigateurs.
for (let item of arr) – la syntaxe moderne pour les éléments uniquement,
for (let i in arr) – ne jamais utiliser.
Pour comparer des tableaux, n'utilisez pas l'opérateur == (ainsi que > , < et autres), car ils n'ont pas de traitement spécial pour les tableaux. Ils les manipulent comme n'importe quel objet, et ce n'est pas ce que nous souhaitons habituellement.
Au lieu de cela, vous pouvez utiliser la boucle for..of pour comparer les tableaux élément par élément.
Nous continuerons avec les tableaux et étudierons d'autres méthodes pour ajouter, supprimer, extraire des éléments et trier des tableaux dans le prochain chapitre Méthodes de tableau.
importance : 3
Que va montrer ce code ?
laissez fruits = ["Pommes", "Poire", "Orange"];
// pousse une nouvelle valeur dans la "copie"
laissez shoppingCart = fruits;
shoppingCart.push("Banane");
// qu'y a-t-il dans les fruits ?
alert( fruits.length ); // ?
Le résultat est 4 :
laissez fruits = ["Pommes", "Poire", "Orange"];
laissez shoppingCart = fruits;
shoppingCart.push("Banane");
alert( fruits.length ); // 4 C'est parce que les tableaux sont des objets. Ainsi, shoppingCart et fruits sont des références au même tableau.
importance : 5
Essayons 5 opérations sur les tableaux.
Créez un tableau styles avec les éléments « Jazz » et « Blues ».
Ajoutez « Rock-n-Roll » à la fin.
Remplacez la valeur au milieu par « Classiques ». Votre code pour trouver la valeur médiane devrait fonctionner pour tous les tableaux de longueur impaire.
Supprimez la première valeur du tableau et affichez-la.
Ajoutez Rap et Reggae au tableau.
Le tableau en cours :
Jazz, Bleu Jazz, Blues, Rock'n'Roll Jazz, Classiques, Rock'n'Roll Classiques, Rock'n'Roll Rap, Reggae, Classiques, Rock-n-Roll
laissez styles = ["Jazz", "Blues"];
styles.push("Rock-n-Roll");
styles[Math.floor((styles.length - 1) / 2)] = "Classiques";
alert( styles.shift() );
styles.unshift("Rap", "Reggae");importance : 5
Quel est le résultat ? Pourquoi?
laissez arr = ["a", "b"];
arr.push(fonction() {
alerter(ceci);
});
arr[2](); // ?
L'appel arr[2]() est syntaxiquement le bon vieux obj[method]() , dans le rôle d' obj nous avons arr , et dans le rôle de method nous avons 2 .
Nous avons donc un appel de la fonction arr[2] comme méthode objet. Naturellement, il reçoit this référencement à l'objet arr et génère le tableau :
laissez arr = ["a", "b"];
arr.push(fonction() {
alerter(ceci);
})
arr[2](); // a,b,fonction(){...}Le tableau a 3 valeurs : initialement il en avait deux, plus la fonction.
importance : 4
Écrivez la fonction sumInput() qui :
Demande à l'utilisateur des valeurs à l'aide prompt et stocke les valeurs dans le tableau.
Termine de demander lorsque l'utilisateur entre une valeur non numérique, une chaîne vide ou appuie sur « Annuler ».
Calcule et renvoie la somme des éléments du tableau.
PS Un zéro 0 est un nombre valide, merci de ne pas arrêter la saisie sur zéro.
Exécutez la démo
Veuillez noter le détail subtil mais important de la solution. Nous ne convertissons pas value en nombre instantanément après prompt , car après value = +value nous ne serions pas en mesure de distinguer une chaîne vide (panneau d'arrêt) du zéro (nombre valide). Nous le faisons plus tard.
fonction sumInput() {
soit les nombres = [];
tandis que (vrai) {
let value = prompt("Un numéro s'il vous plaît ?", 0);
// faut-il annuler ?
if (value === "" || value === null || !isFinite(value)) break;
nombres.push(+valeur);
}
soit somme = 0 ;
pour (soit le nombre de nombres) {
somme += nombre ;
}
retourner la somme ;
}
alerte( sumInput() );importance : 2
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 d'éléments.
Écrivez la fonction getMaxSubSum(arr) qui renverra 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 (tout prendre)
Si tous les éléments sont négatifs, cela signifie que nous n’en prenons aucun (le sous-tableau est vide), donc la somme est nulle :
getMaxSubSum([-1, -2, -3]) = 0
Veuillez essayer de penser à une solution rapide : O(n 2 ) ou même O(n) si vous le pouvez.
Ouvrez un bac à sable avec des tests.
Nous pouvons calculer toutes les sous-sommes 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] :
// A partir de -1 : -1 -1 + 2 -1 + 2 + 3 -1 + 2 + 3 + (-9) -1 + 2 + 3 + (-9) + 11 // A partir de 2 : 2 2 + 3 2 + 3 + (-9) 2 + 3 + (-9) + 11 // A partir de 3 : 3 3 + (-9) 3 + (-9) + 11 // À partir de -9 -9 -9 + 11 // À partir du 11 11
Le code est en fait une boucle imbriquée : la boucle externe sur les éléments du tableau et la boucle interne compte les sous-sommes en commençant par l'élément actuel.
fonction getMaxSubSum(arr) {
soit maxSum = 0 ; // si on ne prend aucun élément, zéro sera renvoyé
pour (soit i = 0; i < arr.length; i++) {
soit sumFixedStart = 0 ;
pour (soit j = i; j < arr.length; j++) {
sumFixedStart += arr[j];
maxSum = Math.max(maxSum, sumFixedStart);
}
}
renvoie la somme maximale ;
}
alerte( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alerte( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alerte( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alerte( getMaxSubSum([1, 2, 3]) ); // 6
alerte( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100La solution a une complexité temporelle de O(n 2 ). 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 entraîner de sérieuses lenteurs.
Parcourons le tableau et gardons la somme partielle actuelle des éléments dans la variable s . Si s devient négatif à un moment donné, alors attribuez s=0 . Le maximum de toutes ces s sera la réponse.
Si la description est trop vague, merci de consulter le code, il est assez court :
fonction getMaxSubSum(arr) {
soit maxSum = 0 ;
soit partialSum = 0 ;
for (let item of arr) { // pour chaque élément de arr
partialSum += élément ; // l'ajoute à partialSum
maxSum = Math.max(maxSum, partialSum); // mémorise le maximum
si (partialSum < 0) partialSum = 0 ; // zéro si négatif
}
renvoie la somme maximale ;
}
alerte( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alerte( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alerte( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alerte( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100
alerte( getMaxSubSum([1, 2, 3]) ); // 6
alerte( getMaxSubSum([-1, -2, -3]) ); // 0L'algorithme nécessite exactement 1 passage de tableau, donc la complexité temporelle est O(n).
Vous pouvez trouver des informations plus détaillées sur l'algorithme ici : Problème de sous-tableau maximum. Si la raison pour laquelle cela fonctionne n'est toujours pas évidente, veuillez tracer l'algorithme sur les exemples ci-dessus, voir comment il fonctionne, c'est mieux que n'importe quel mot.
Ouvrez la solution avec des tests dans un bac à sable.