Maximum Subarray

Un sous-tableau est une suite d’éléments voisins d’une liste, sans aucun élément manquant entre eux. Parmi tous les sous-tableaux non vides d’une liste d’entiers, tu veux celui dont les éléments ont la somme la plus élevée, et tu renvoies cette somme.

Dans [2, -4, 3, -1, 5, -6, 1], la meilleure suite est [3, -1, 5], dont la somme vaut 7. Elle conserve le -1 parce que le 5 qui le suit compense largement sa valeur, et elle laisse de côté le 2 du début parce que le -4 qui suit coûte plus que ce que le 2 rapporte.

La solution classique en un seul parcours est l’algorithme de Kadane. Parcours la liste et conserve la meilleure somme d’une suite qui se termine à l’élément courant. À chaque élément, il n’y a que deux possibilités : prolonger la suite qui se terminait à l’élément précédent, ou recommencer avec une nouvelle suite qui commence ici. Prolonger n’est avantageux que tant que la suite précédente a une somme positive ; dès que cette somme tombe à zéro ou en dessous, la conserver ne peut que nuire, alors tu repars de zéro. La réponse est la plus grande somme de suite rencontrée au cours du parcours.

Pour l’exemple, les meilleures sommes de suites se terminant à chaque position sont 2, -2, 3, 2, 7, 1 et 2 ; la réponse est donc 7. Chaque élément est examiné une seule fois, le travail augmente donc de façon linéaire avec la longueur de la liste.

Écrivez une fonction nommée maxSubArray qui reçoit une liste d’entiers nums et renvoie la plus grande somme d’un sous-tableau contigu non vide de nums.

Contraintes : 1 ≤ nums.length ≤ 10^5, -10^4 ≤ nums[i] ≤ 10^4.