Sous-tableau de somme maximale et sous-tableau de produit maximal

Le problème du sous-tableau de somme maximale vous demande de trouver, dans un tableau unidimensionnel de nombres, le sous-tableau contigu dont la somme est la plus grande. Par exemple, dans [-2, 1, -3, 4, -1, 2, 1, -5, 4], le sous-tableau [4, -1, 2, 1] donne la somme maximale, soit 6. Une approche par force brute en O(n²) vérifie tous les sous-tableaux, mais l'algorithme de Kadane résout ce problème en O(n).

L'algorithme de Kadane parcourt le tableau une seule fois en maintenant une current_sum cumulative. À chaque élément, vous devez décider s'il vaut mieux étendre le sous-tableau existant ou recommencer à partir de cet élément. Si current_sum devient négative, elle ne ferait que nuire à tout sous-tableau futur : il faut donc recommencer. La récurrence est current_sum = max(num, current_sum + num).

Suivons l'algorithme de Kadane sur [-2, 1, -3, 4, -1, 2, 1, -5, 4] : au départ, la somme courante vaut -2 et le maximum vaut -2. Pour 1, la somme courante devient 1 et le maximum vaut 1. Pour -3, la somme courante devient -2 et le maximum reste 1. Pour 4, la somme courante devient 4 et le maximum vaut 4. Pour -1, la somme courante vaut 3 et le maximum reste 4. Pour 2, la somme courante vaut 5 et le maximum devient 5. Pour 1, la somme courante vaut 6 et le maximum devient 6. Pour -5, la somme courante vaut 1. Pour 4, elle vaut 5 et le maximum reste 6. L'algorithme identifie correctement le sous-tableau se terminant à l'indice 6 comme étant optimal.

Si l'intervieweur vous demande de renvoyer le sous-tableau lui-même (et pas seulement la somme), vous devez suivre les indices de début et de fin. Lorsque vous recommencez (car num > current_sum + num), mettez à jour un temp_start. Lorsque vous mettez à jour max_sum, enregistrez temp_start comme start et l'indice courant comme end. Cela ajoute un surcoût de O(1) au même algorithme en O(n).

Le problème du sous-tableau de produit maximal est plus délicat que sa variante fondée sur la somme à cause des nombres négatifs. Deux nombres négatifs donnent un produit positif : un produit très négatif peut donc devenir le maximum après une nouvelle multiplication par un nombre négatif. Pour [2, 3, -2, 4], le résultat est 6 ([2, 3]). Pour [-2, 0, -1], le résultat est 0. Nous devons suivre à chaque étape les produits maximum et minimum.

L'idée clé est la suivante : à chaque position, le produit maximal courant est l'une des valeurs num, max_so_far * num ou min_so_far * num (cette dernière aide lorsqu'un nombre négatif transforme le minimum en maximum). Il en va de même pour le minimum. Mettez à jour simultanément cur_max et cur_min à partir des valeurs précédentes afin de ne pas utiliser, au cours de la même étape, des valeurs déjà mises à jour.

Considérez [-3, -10, 5]. Après le traitement de -3 : maximum = -3, minimum = -3. Après -10 : les candidats sont (-10, 30, 30) → maximum = 30, minimum = -10. Après 5 : les candidats sont (5, 150, -50) → maximum = 150. Sans suivre min_prod, vous manqueriez l'inversion qui se produit lorsqu'un minimum très négatif est multiplié par un autre nombre négatif. Calculez toujours max et min à partir des mêmes valeurs précédentes afin d'éviter un problème de lecture de valeurs obsolètes.

Un zéro dans le tableau réinitialise les deux produits cumulés à zéro, ce qui sépare effectivement le tableau en sous-tableaux indépendants. Lorsque num = 0, max_prod * 0 = 0 et min_prod * 0 = 0 : les trois candidats deviennent donc 0, et le maximum du résultat précédent est conservé. Aucun traitement particulier n'est nécessaire : la formule générale gère naturellement les zéros.

Une autre approche effectue un parcours de gauche à droite, puis de droite à gauche, en réinitialisant le produit cumulé à 1 lorsqu'il rencontre un zéro. Le sous-tableau de produit maximal ne traverse jamais un zéro ; ainsi, si un nombre négatif dégrade le résultat dans une direction, le parcours inverse détectera l'inversion. Cette approche est élégante, mais la méthode de suivi du minimum et du maximum est plus souvent attendue lors des entretiens.

Les sous-tableaux fondés sur une somme et ceux fondés sur un produit diffèrent de manière importante. Pour la somme, les nombres négatifs sont toujours nuisibles : vous recommencez donc de manière gloutonne. Pour le produit, deux nombres négatifs sont avantageux : vous devez donc suivre les deux extrêmes. De plus, les zéros sont terminaux pour les produits, mais seulement légèrement nuisibles pour les sommes. Lors d'un entretien, reconnaissez explicitement ces différences et expliquez pourquoi il est nécessaire de suivre le minimum avant d'écrire du code.

L'algorithme de Kadane (somme maximale) et le suivi du minimum et du maximum (produit maximal) s'exécutent tous deux en temps O(n) et utilisent un espace O(1). Conseils importants pour les entretiens : (1) Pour la somme maximale, mentionnez l'alternative « diviser pour régner » en O(n log n) afin de montrer l'étendue de vos connaissances. (2) Pour le produit maximal, insistez sur le fait que vous mettez à jour min_prod et max_prod simultanément à partir des valeurs précédentes, afin de ne pas utiliser de données obsolètes. (3) Clarifiez toujours les points suivants : le tableau peut-il être vide ? Le sous-tableau doit-il être non vide ? (Oui, par convention, il doit être non vide.)

Évaluez votre compréhension des concepts de structures de données et d'algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.

Dans cette leçon, vous avez appris : l'algorithme de Kadane résout le problème du sous-tableau de somme maximale en O(n) en choisissant, pour chaque élément, de prolonger le sous-tableau ou de recommencer, le sous-tableau de produit maximal nécessite de suivre simultanément les produits cumulés minimum et maximum en raison des inversions causées par les nombres négatifs, et les zéros réinitialisent naturellement le produit cumulé sans traitement particulier. Ensuite, nous étudierons le problème de la segmentation de mots à l'aide d'une table de DP à une dimension.