Kadane en entretien : expliquer le maximum subarray

Maîtrisez le maximum subarray en entretien avec une explication claire de Kadane, un dry run et les cas pièges. Préparez-vous à répondre sans hésiter.

Most candidates qui se figent face à la question d’entretien sur le maximum subarray ne se figent pas parce qu’ils ont oublié l’algorithme. Ils se figent parce que personne ne leur a jamais demandé d’énoncer la réponse à voix haute avant d’écrire la moindre ligne de code — et l’écart entre « je sais comment ça marche » et « je peux l’expliquer clairement à quelqu’un en temps réel » est bien plus grand qu’il n’y paraît jusqu’au moment où vous êtes assis en face d’un recruteur.

Ce guide vous propose un script court et reproductible : une manière d’ouvrir le sujet, de dériver la solution optimale à partir du brute force, de faire un dry run de l’exemple standard, et de gérer tous les suivis probables sans donner l’impression de réciter un manuel. Lisez-le une fois, puis dites-le à voix haute. Tout le plan d’entraînement tient là.

Dites ce qu’est le problème avant de toucher au code

Pourquoi les gens trébuchent sur la première phrase

L’erreur la plus fréquente dans une réponse à un problème de maximum subarray n’est pas de se tromper d’algorithme — c’est de sauter complètement la définition du problème pour foncer directement sur le code. Les recruteurs le remarquent immédiatement. Cela signale que le candidat a reconnu un schéma et ressorti une solution mémorisée, plutôt que de raisonner réellement sur le problème. Et cela rend la réponse fragile : dès que le recruteur modifie une contrainte, le candidat n’a plus rien sur quoi s’appuyer.

Le point précis que beaucoup oublient de définir, c’est ce que signifie « contiguous ». Un sous-tableau contigu est une suite d’éléments qui apparaissent consécutivement dans le tableau d’origine — vous ne pouvez ni sauter des éléments ni en changer l’ordre. Le résultat recherché est la somme maximale que vous pouvez obtenir sur n’importe quel sous-tableau de ce type, y compris les sous-tableaux de longueur un. Selon Introduction to Algorithms (CLRS), le problème du maximum subarray est défini exactement dans ces termes, et cette définition est essentielle : elle exclut l’approche gloutonne « prendre tous les positifs » et rend le problème intéressant.

À quoi cela ressemble en pratique

Voici l’ouverture de 60 secondes que vous voulez donner avant de toucher au code :

« L’entrée est un tableau d’entiers pouvant contenir des nombres positifs et négatifs. La sortie est la somme maximale que l’on peut obtenir à partir de n’importe quel sous-tableau contigu — autrement dit, on choisit un indice de départ et un indice de fin, puis on additionne tous les éléments entre les deux. On peut choisir un seul élément, mais on ne peut ni sauter d’éléments ni boucler. Pour l’exemple [-2, 1, -3, 4, -1, 2, 1, -5, 4], la réponse est 6, obtenue avec le sous-tableau [4, -1, 2, 1]. Je vais commencer par l’approche brute force pour vérifier que j’ai le bon modèle mental, puis nous regarderons une solution plus efficace. »

C’est tout. Quarante-cinq secondes, une entrée et une sortie claires, un exemple concret et une feuille de route qui montre que vous allez raisonner sur le problème plutôt que réciter une solution apprise par cœur. Le recruteur sait que vous comprenez ce que vous cherchez à résoudre avant même que vous ayez écrit un caractère.

Commencez par le brute force pour que la meilleure réponse fasse sens

L’idée brute force n’est pas idiote — c’est le pont

L’approche en O(n²) a mauvaise réputation dans la préparation aux entretiens, surtout parce que les candidats la traitent comme une ébauche honteuse dont ils doivent s’excuser avant de passer à la « vraie » réponse. C’est une mauvaise manière de voir les choses. Le brute force est utile non pas parce qu’il est rapide — il ne l’est évidemment pas — mais parce qu’il rend la somme maximale de sous-tableau concrète. Il montre exactement ce que vous mesurez avant de chercher à le mesurer efficacement.

L’idée brute force est simple : pour chaque indice de départ possible, on étend le sous-tableau un élément à la fois, en suivant la somme courante et en mettant à jour le meilleur résultat vu jusqu’ici. Deux boucles imbriquées, sans subtilité. La boucle externe choisit le départ, la boucle interne étend jusqu’à chaque fin possible. Vous gardez un maximum global et vous le renvoyez à la fin.

À quoi cela ressemble en pratique

Prenons le tableau [-2, 1, -3, 4, -1]. En partant de l’indice 0 : le sous-tableau [-2] donne -2, [-2,1] donne -1, [-2,1,-3] donne -4, [-2,1,-3,4] donne 0, [-2,1,-3,4,-1] donne -1. En partant de l’indice 1 : [1] donne 1, [1,-3] donne -2, [1,-3,4] donne 2, [1,-3,4,-1] donne 1. Et ainsi de suite.

Ce que vous remarquez immédiatement, c’est que chaque fois que vous prolongez à partir du même indice de départ, vous n’ajoutez qu’un élément à la somme courante. Vous ne repartez pas de zéro — vous prolongez. Cette observation est précisément la graine de la solution efficace.

La récurrence cachée dans le brute force

Dès que vous voyez que la boucle interne revient à « continuer à additionner à la même somme courante », vous pouvez poser une question plus fine : ai-je vraiment besoin de relancer la boucle externe à chaque fois ? Si la somme courante est devenue si négative qu’elle pénalise tout ce qui suit, la bonne décision est de l’abandonner et de repartir du élément courant. Si la somme courante est encore positive, il est avantageux de la conserver.

Cette décision — prolonger ou repartir à zéro — est tout l’esprit de l’algorithme de Kadane, qui est formellement une récurrence de programmation dynamique : le maximum d’un sous-tableau se terminant à l’indice i est soit l’élément en i pris seul, soit l’élément en i additionné au maximum du sous-tableau se terminant à i-1. Vous réduisez les deux boucles imbriquées à un seul passage, parce que vous avez identifié que l’état de la boucle interne peut être propagé plutôt que recalculé.

Utilisez le script Kadane que le recruteur veut entendre

Pourquoi la règle de réinitialisation paraît étrange jusqu’à ce qu’on l’énonce à voix haute

La règle de réinitialisation est l’élément que les candidats expliquent le plus souvent maladroitement quand ils présentent l’algorithme de Kadane. Ils disent quelque chose comme « on réinitialise quand la somme devient négative », ce qui est proche, mais pas tout à fait juste — et un recruteur expérimenté creusera immédiatement. La formulation plus précise est la suivante : dès que la somme courante est négative, la conserver pour l’élément suivant dégrade sa contribution par rapport au fait de repartir de zéro. Un préfixe négatif est strictement défavorable. Repartir de l’élément courant est toujours au moins aussi bon que de propager une somme négative.

Ce n’est ni une astuce ni une heuristique. C’est une conséquence de la récurrence : `current_max = max(nums[i], current_max + nums[i])`. Quand `current_max` est négatif, `nums[i]` seul est supérieur à `current_max + nums[i]`, donc on choisit `nums[i]` seul. La réinitialisation n’est que la traduction mathématique de cela.

À quoi cela ressemble en pratique

Voici l’explication à mémoriser — dites-la à voix haute avant l’entretien :

« Je vais garder deux variables : current_sum, qui est la somme maximale d’un sous-tableau se terminant à l’indice courant, et best_sum, qui est le meilleur résultat vu partout jusqu’ici. À chaque indice, je me demande : vaut-il mieux prolonger le sous-tableau courant, ou repartir de cet élément ? C’est simplement prendre le maximum entre l’élément courant seul et l’élément courant plus current_sum. Après avoir mis à jour current_sum, je mets à jour best_sum si current_sum est plus grand. Un seul passage, espace constant, temps O(n). »

C’est tout le script. Il est précis, il nomme les variables, il explique la décision, et il ne sonne pas comme une récitation parce que vous décrivez une décision à chaque étape plutôt qu’une procédure mécanique.

La phrase qui distingue une bonne réponse d’une réponse apprise par cœur

Le signe distinctif qu’un recruteur utilise souvent pour distinguer une réponse raisonnée d’une réponse mémorisée, c’est de savoir si le candidat peut expliquer ce qui se passe à un indice précis. « À l’indice 3, current_sum est négative, donc on réinitialise à nums[3] » est une réponse raisonnée. « On réinitialise quand la somme devient négative » est un slogan. Entraînez-vous à raconter la décision à chaque indice pendant votre dry run — cette narration est ce qui rend l’explication vivante plutôt que récité.

La couverture de l’algorithme de Kadane par GeeksforGeeks confirme les assertions de complexité en O(n) temps et O(1) espace et mérite d’être consultée pour vérifier que votre nommage des variables reste conforme aux conventions courantes.

Faites un dry run de l’exemple standard sans perdre le fil

L’exemple que tous les recruteurs semblent adorer

Le tableau [-2, 1, -3, 4, -1, 2, 1, -5, 4] est l’exemple canonique pour une bonne raison : il contient plusieurs réinitialisations, une longue séquence d’extensions profitables, et un élément positif trompeur à la fin qui ne fait pas partie du sous-tableau contigu optimal. Il teste votre compréhension réelle de la décision à chaque étape, ou au contraire votre simple réflexe à « prendre les gros nombres ».

La bonne réponse est 6, obtenue avec le sous-tableau contigu [4, -1, 2, 1] à partir de l’indice 3.

À quoi cela ressemble en pratique

Suivez-le indice par indice, en commentant au fur et à mesure :

• Indice 0, valeur -2 : current_sum = max(-2, -2) = -2. best_sum = -2.
• Indice 1, valeur 1 : current_sum = max(1, -2+1) = max(1, -1) = 1. Réinitialisation. best_sum = 1.
• Indice 2, valeur -3 : current_sum = max(-3, 1-3) = max(-3, -2) = -2. best_sum = 1.
• Indice 3, valeur 4 : current_sum = max(4, -2+4) = max(4, 2) = 4. Réinitialisation. best_sum = 4.
• Indice 4, valeur -1 : current_sum = max(-1, 4-1) = max(-1, 3) = 3. Extension. best_sum = 4.
• Indice 5, valeur 2 : current_sum = max(2, 3+2) = 5. Extension. best_sum = 5.
• Indice 6, valeur 1 : current_sum = max(1, 5+1) = 6. Extension. best_sum = 6.
• Indice 7, valeur -5 : current_sum = max(-5, 6-5) = 1. Extension. best_sum = 6.
• Indice 8, valeur 4 : current_sum = max(4, 1+4) = 5. Extension. best_sum = 6.

Réponse finale : 6. Les moments pédagogiques clés sont les réinitialisations aux indices 1 et 3, et le fait que le 4 final à l’indice 8 ne dépasse pas le meilleur résultat trouvé auparavant. Commentez ces moments explicitement — ne vous contentez pas d’écrire des nombres sur un tableau blanc en espérant que le recruteur suive.

Anticipez les suivis avant qu’ils ne deviennent des pièges

Le cas où tous les éléments sont négatifs est celui où une initialisation maladroite casse tout

Si vous initialisez best_sum à zéro, vous renverrez zéro pour un tableau entièrement négatif comme [-3, -1, -2]. C’est faux — la bonne réponse est -1, parce que le problème demande la somme maximale d’un sous-tableau et qu’un sous-tableau d’un seul élément est valide. Zéro n’est atteignable par aucun sous-tableau contigu dans cette entrée.

La correction consiste à initialiser best_sum avec le premier élément du tableau, pas avec zéro. Ou, de manière équivalente, à l’initialiser à moins l’infini. Ce n’est pas un détail mineur — c’est un test délibéré visant à vérifier que vous comprenez réellement les contraintes du problème au lieu d’avoir mémorisé une solution adaptée aux exemples dominés par les positifs. Dans un entretien sur le maximum subarray, ce suivi apparaît suffisamment souvent pour que vous le traitiez comme faisant partie de la réponse de base, et non comme un cas annexe.

À quoi cela ressemble en pratique

Voici un script de suivi qui couvre en une seule passe la complexité, l’initialisation et l’erreur de réinitialisation :

« La complexité temporelle est O(n) — un seul passage sur le tableau. La complexité spatiale est O(1) — nous ne suivons que deux variables, indépendamment de la taille d’entrée. Pour le cas entièrement négatif, le point clé est l’initialisation : best_sum commence à nums[0], pas à zéro, afin de renvoyer l’élément le moins négatif plutôt qu’un zéro fictif. La règle de réinitialisation reste valable — on réinitialise quand current_sum risquerait de pénaliser l’élément suivant — mais dans un tableau tout négatif, on réinitialisera à presque chaque étape, et c’est bien le comportement attendu. »

Cette réponse couvre simultanément trois axes de suivi. Les recruteurs qui posent la question du cas tout négatif vérifient précisément votre initialisation — une réponse propre ici montre que vous avez réfléchi au problème plutôt que copié une solution.

Renvoyer les bornes est un petit changement, pas un nouveau problème

Quand un recruteur vous demande de renvoyer le sous-tableau lui-même plutôt que sa seule somme, les candidats paniquent souvent et se tournent vers une approche complètement différente. Ne le faites pas. La même logique en O(n) s’applique — vous ajoutez simplement trois variables : start (le début candidat du sous-tableau courant), end (la fin courante), et best_start (le début confirmé du meilleur sous-tableau vu jusqu’ici).

Lorsque vous réinitialisez current_sum à nums[i], mettez start à i. Lorsque vous mettez à jour best_sum, enregistrez best_start = start et end = i. À la fin, renvoyez nums[best_start:end+1]. L’algorithme ne change pas. Le suivi d’état ajoute trois variables et quelques lignes d’affectation. Présentez-le exactement comme cela au recruteur : « C’est le même algorithme avec un peu de gestion d’état en plus — je vais suivre le début de la fenêtre courante et mettre à jour les bornes confirmées à chaque nouveau meilleur résultat. »

Le chapitre 4 de CLRS traite en détail du problème du maximum subarray et constitue la référence de fond pour l’analyse de complexité si vous souhaitez citer une source pendant un entretien technique.

Utilisez la réponse comme modèle pour des variantes plus larges

Pourquoi le recruteur peut vous demander une variante plutôt que la réponse de base

Une fois que vous avez donné une explication claire de Kadane, certains recruteurs passent à une variante — non pour vous piéger, mais pour vérifier si vous comprenez la structure sous-jacente ou seulement la solution en surface. La variante la plus courante est la somme maximale de sous-tableau circulaire : quelle est la somme maximale si le tableau « boucle » (c’est-à-dire si le sous-tableau peut aller de la fin du tableau jusqu’au début) ?

À quoi cela ressemble en pratique

La variante circulaire a une solution élégante qui réutilise deux fois l’algorithme de Kadane. La somme maximale dans un tableau circulaire est soit :

• La somme maximale standard du sous-tableau (la réponse ne boucle pas), soit
• La somme totale du tableau moins la somme minimale d’un sous-tableau (la réponse boucle, donc on exclut le segment central minimal)

Vous exécutez Kadane dans le sens direct pour obtenir le maximum, puis une version de Kadane pour le minimum de sous-tableau (en inversant les comparaisons) pour obtenir le minimum, vous le soustrayez du total, et vous prenez la plus grande des deux valeurs. Un cas limite : si tous les éléments sont négatifs, l’option 2 donnerait zéro (total moins total), donc dans ce cas on renvoie l’option 1.

Le point à faire passer au recruteur : « La variante circulaire réutilise la même logique en O(n) — je ne cherche pas un nouvel algorithme, j’applique la même structure de décision deux fois avec des objectifs différents. » Ce cadrage montre que vous voyez Kadane comme un motif, et non comme une réponse mémorisée. Pour un traitement détaillé de la variante circulaire, LeetCode Problem 918 fournit un énoncé canonique et des solutions de la communauté qui valent la peine d’être étudiées.

Comment Verve AI peut vous aider à préparer votre entretien sur le maximum subarray

Le problème structurel que ce guide cherche à résoudre — connaître l’algorithme mais bafouiller dans l’explication sous pression — ne se corrige qu’avec de la répétition accompagnée de retours, pas par la lecture seule. Un script lu une fois s’effondre dès qu’un recruteur demande : « pourquoi cette réinitialisation fonctionne-t-elle déjà ? » Vous devez dire l’explication à voix haute, vous entendre la formuler, et recevoir une réponse qui reflète les vraies objections d’un recruteur.

Verve AI Interview Copilot est conçu pour combler exactement cet écart. Il écoute en temps réel votre explication pendant que vous la donnez — pas une réponse tapée à l’avance, mais ce que vous dites réellement — et réagit à ce que vous avez dit, y compris aux passages que vous avez survolés ou aux transitions qui n’ont pas pris. Si vous avez dit « on réinitialise quand la somme est négative » en omettant la discussion sur l’initialisation, Verve AI Interview Copilot le repèrera comme le ferait un recruteur réel. La boucle de pratique, c’est la conversation en direct, pas un quiz à choix multiples.

Verve AI Interview Copilot anime aussi des entretiens blancs sur toute la séquence : définition du problème, walkthrough brute force, dérivation de Kadane, dry run, suivis. Vous pouvez répéter l’ouverture de 60 secondes, être interrompu au milieu de l’explication et vous entraîner à rebondir — ce qui est la compétence réellement testée en entretien. L’outil reste invisible pendant que vous travaillez sur le problème, de sorte que la séance ressemble à un véritable entretien plutôt qu’à un outil de préparation avec petites roulettes.

FAQ

Q : Comment puis-je expliquer le maximum subarray de manière claire et convaincante en entretien ?

Commencez par définir le problème avant de toucher au code : nommez l’entrée, définissez ce que signifie « contiguous », indiquez la sortie attendue et donnez un exemple concret avec la bonne réponse. Cette ouverture de 45 secondes montre au recruteur que vous raisonnez sur le problème plutôt que de réciter une solution mémorisée. Dites ensuite que vous commencerez par le brute force avant de construire la solution efficace.

Q : Comment dériver l’algorithme de Kadane à partir de l’approche brute force ?

La boucle interne du brute force revient simplement à « continuer à additionner à la même somme courante à partir d’un indice de départ fixé ». Une fois cela compris, vous pouvez vous demander : dois-je vraiment relancer la boucle externe à chaque fois, ou puis-je propager la somme courante ? Si la somme courante est positive, la conserver aide les éléments suivants. Si elle est négative, repartir de l’élément courant est toujours préférable. Cette décision — prolonger ou repartir — constitue toute la récurrence derrière l’algorithme de Kadane.

Q : Pourquoi réinitialise-t-on la somme courante quand elle devient moins bonne que de repartir de zéro ?

Parce qu’un préfixe négatif réduit strictement la contribution de tous les éléments qui suivent. La récurrence est `current_sum = max(nums[i], current_sum + nums[i])`. Quand current_sum est négative, `nums[i]` seul est supérieur à `current_sum + nums[i]`, donc les mathématiques vous disent de réinitialiser. Ce n’est pas une heuristique — c’est une conséquence directe de la récurrence.

Q : Comment gérer un tableau où tous les nombres sont négatifs ?

Initialisez best_sum avec le premier élément du tableau, pas avec zéro. Dans un tableau tout négatif, la bonne réponse est le plus grand élément pris seul — zéro n’est atteignable par aucun sous-tableau contigu. Si vous initialisez à zéro, vous obtiendrez une mauvaise réponse. L’algorithme s’exécute sinon de la même manière ; vous réinitialiserez simplement à presque chaque étape.

Q : Comment faire un dry run de l’exemple standard sans perdre le fil ?

Suivez deux colonnes : current_sum et best_sum. À chaque indice, appliquez la récurrence pour mettre à jour current_sum, puis vérifiez s’il bat best_sum. Commentez la décision à voix haute — « à l’indice 3, current_sum est devenue négative, donc je réinitialise à 4 » — au lieu d’écrire simplement des nombres. C’est cette narration que le recruteur écoute réellement.

Q : Que dois-je dire si le recruteur me demande la complexité temporelle et spatiale, et pourquoi ?

O(n) en temps parce que vous faites exactement un passage sur le tableau. O(1) en espace parce que vous ne suivez que deux variables — current_sum et best_sum — quelle que soit la taille de l’entrée. Le « pourquoi » compte : vous ne stockez ni sous-tableaux intermédiaires ni structures de données auxiliaires. L’espace constant découle directement du fait que la récurrence n’a besoin que du résultat de l’étape précédente.

Q : Comment renvoyer les bornes du sous-tableau au lieu de la seule somme ?

Suivez trois variables supplémentaires : un indice de début candidat (mis à jour à chaque réinitialisation), ainsi que des indices de début et de fin confirmés (mis à jour à chaque nouveau best_sum). L’algorithme reste en O(n) avec O(1) d’espace — vous faites simplement quelques affectations de plus à chaque étape. Présentez cela au recruteur comme du suivi d’état ajouté à la même logique, et non comme un nouvel algorithme.

Le script est maintenant dans votre poche

La pression d’une question d’entretien sur le maximum subarray ne vient pas de l’algorithme — elle vient du moment juste avant de commencer à écrire, lorsque vous devez dire quelque chose de cohérent à quelqu’un qui vous regarde réfléchir. C’est ce moment que ce guide visait à préparer. Vous avez maintenant une ouverture de 60 secondes qui définit proprement le problème, une dérivation qui montre que vous comprenez pourquoi l’algorithme de Kadane fonctionne et pas seulement qu’il fonctionne, un dry run pas à pas que vous pouvez suivre sans perdre le fil, et un script de suivi serré qui couvre l’initialisation, la complexité et le suivi des indices sans vous déstabiliser.

Répétez l’explication de 60 secondes une fois avant votre prochain entretien — pas dix fois. Un passage volontaire à voix haute, en commentant la décision à chaque indice, vaut plus que dix relectures silencieuses de cette page.