Maximum Sum Subarray of Size K

Q: Qu’est-ce qu’une fenêtre glissante de taille fixe ?

Il s’agit d’une plage de exactement k éléments voisins qui se déplace d’un pas à la fois dans un tableau. Au lieu de recalculer la plage depuis le début à chaque position, vous mettez à jour une valeur courante : ajoutez l’élément qui entre par la droite et retirez celui qui sort par la gauche. Cela transforme un travail de O(n·k) en O(n) .

Q: En quoi est-ce différent du problème du sous-tableau de somme maximale ?

Ici, la longueur est fixe à k , donc chaque candidat est une fenêtre et une somme glissante les couvre tous. Dans le problème du sous-tableau de somme maximale, la longueur est libre, et il te faut l’algorithme de Kadane, qui décide à chaque élément s’il faut prolonger la séquence actuelle ou en commencer une nouvelle. Une fenêtre fixe n’offre jamais ce choix.

Q: Les sommes préfixes peuvent-elles aussi résoudre ce problème ?

Oui. Construisez prefix[i] comme la somme des i premiers éléments, et la fenêtre commençant à s a pour somme prefix[s+k] - prefix[s] . Cela prend aussi un temps de O(n) , mais stocke n+1 totaux. La fenêtre glissante obtient les mêmes sommes avec deux variables.

FacileFenêtre glissante

+10

Vous recevez un tableau d’entiers nums et une longueur de fenêtre k. Examinez chaque séquence de exactement k éléments voisins et renvoyez la somme la plus élevée parmi elles. Les valeurs peuvent être négatives, donc la réponse peut l’être aussi.

Fonction

maxSumSubarray(nums: integer-array, k: integer) → integer

numsinteger-array: le tableau d’entiers
kinteger: combien d’éléments voisins contient chaque fenêtre
Renvoieinteger: la plus grande somme de k éléments consécutifs

Contraintes

1 ≤ k ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴

Exemples

Entrée: nums = [4, -1, 3, 7, -2, 5, 1]k = 3
Sortie: 10
Explication: Les cinq fenêtres de longueur 3 donnent 6, 9, 8, 10 et 4. La plus grande somme est 7 + (-2) + 5 = 10.

Entrée: nums = [-3, -8, -1, -6]k = 2
Sortie: -7
Explication: Toutes les valeurs sont négatives, donc chaque somme de fenêtre l’est aussi : -11, -9 et -7. La plus grande d’entre elles est -1 + (-6) = -7.

Entrée: nums = [5, -2, 4]k = 3
Sortie: 7
Explication: Lorsque k est égal à la longueur du tableau, il y a une fenêtre, le tableau entier, et 5 + (-2) + 4 = 7.

+15 tests cachés à la soumission

Pour aller plus loin

Peux-tu également renvoyer l’indice de début de la meilleure fenêtre, en choisissant la plus à gauche lorsque plusieurs fenêtres sont ex æquo ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Il y a n-k+1 fenêtres, et calculer chacune d’elles depuis zéro coûte k additions. L’astuce, c’est que deux fenêtres voisines se chevauchent à l’exception de deux éléments. Faites glisser la fenêtre au lieu de la reconstruire : une valeur entre, une valeur sort, et chaque somme de fenêtre nécessite deux opérations.

Additionner toutes les fenêtres

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Une fenêtre est définie par son indice de départ. Elle peut commencer à l’indice 0, 1, et ainsi de suite jusqu’à n-k, car un départ plus tardif dépasserait la fin du tableau. Pour chaque départ, additionnez les k éléments et comparez le total au meilleur résultat obtenu jusque-là.

Pour [4, -1, 3, 7, -2, 5, 1] et k = 3, on obtient les sommes 6, 9, 8, 10, 4, et la réponse est 10. Initialisez le meilleur résultat à la somme de la première fenêtre, ou au plus petit entier, jamais à 0 : si toutes les valeurs sont négatives, 0 serait supérieur à toutes les fenêtres réelles.

Le coût est de (n-k+1) × k additions. Il atteint son maximum lorsque k vaut environ la moitié de n : avec n = 10^4 et k = 5000, cela représente 5001 × 5000, soit environ 2.5 × 10^7 additions, et presque toutes répètent le travail effectué pour la fenêtre précédente.

Algorithme

Définissez best à la plus petite valeur possible.
Pour chaque début compris entre 0 et n-k, définissez total = 0.
Ajoutez à total les valeurs de nums[start] à nums[start+k-1].
Si total est supérieur à best, stockez-le.
Renvoyez best.

def maxSumSubarray(nums, k):
    n = len(nums)
    best = None
    for start in range(n - k + 1):
        total = 0
        for i in range(start, start + k):
            total += nums[i]
        if best is None or total > best:
            best = total
    return best

Faites glisser une fenêtre fixe

Intuition

Comparez la fenêtre commençant à l’indice 0 avec celle commençant à l’indice 1. Dans [4, -1, 3, 7, -2, 5, 1] avec k = 3, elles sont 4 + (-1) + 3 = 6 et (-1) + 3 + 7 = 9. Elles contiennent toutes deux -1 et 3. La deuxième somme est la première, à laquelle on ajoute la valeur qui entre, 7, et dont on soustrait la valeur qui sort, 4 : 6 + 7 - 4 = 9.

Cela vaut à chaque étape. Lorsque l’extrémité droite de la fenêtre se déplace vers l’indice i, l’élément à l’indice i entre et l’élément à l’indice i-k sort. Vous calculez donc une seule fois la somme de la première fenêtre, puis vous mettez à jour la somme avec une addition et une soustraction à chaque étape. Les sommes sont 6, 9, 8, 10, 4, comme avec la méthode de force brute, et vous gardez la plus grande.

Chaque élément entre une fois et sort au plus une fois, donc la complexité temporelle est O(n). Vous gardez deux nombres, la somme actuelle de la fenêtre et la meilleure somme, donc l’espace supplémentaire est O(1). Aucune somme ici ne dépasse 10^4 × 10^4 = 10^8, donc un entier sur 32 bits suffit.

Algorithme

Additionne nums[0] jusqu’à nums[k-1] dans window.
Définis best = window.
Pour chaque i de k à n-1, ajoute nums[i] et soustrais nums[i-k].
Après chaque étape, définis best comme la plus grande valeur entre best et window.
Retourne best.

def maxSumSubarray(nums, k):
    # Sum of the first window, nums[0..k-1].
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        # Slide one step right: nums[i] enters, nums[i-k] leaves.
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best

Pièges et cas limites

L’idée de la fenêtre est simple, alors les erreurs se cachent dans les valeurs de départ et les indices.

Initialiser best à 0. Avec [-3, -8, -1, -6] et k = 2, la vraie réponse est -7, mais une valeur de best égale à 0 n’est jamais dépassée et est renvoyée comme réponse.
Soustraire le mauvais élément. Lorsque nums[i] entre, l’élément qui sort est nums[i-k]. Utiliser nums[i-k+1] ou nums[i-k-1] donne des fenêtres de la mauvaise longueur.
Arrêter la recherche exhaustive un départ trop tôt. La dernière fenêtre commence à n-k, donc la boucle doit l’inclure. Avec k = n, c’est la seule fenêtre, et une erreur de décalage d’un indice ne vérifie aucune fenêtre et renvoie la valeur initiale de best.
Comparer uniquement après la boucle. La meilleure fenêtre peut être la première : comparez donc aussi la première somme, ou initialisez best avec celle-ci.
Oublier que R et Lua commencent à compter à 1. La première fenêtre est nums[1..k], et l’élément qui sort lorsque nums[i] entre est toujours nums[i-k].

Questions fréquentes4

Qu’est-ce qu’une fenêtre glissante de taille fixe ?

Il s’agit d’une plage de exactement k éléments voisins qui se déplace d’un pas à la fois dans un tableau. Au lieu de recalculer la plage depuis le début à chaque position, vous mettez à jour une valeur courante : ajoutez l’élément qui entre par la droite et retirez celui qui sort par la gauche. Cela transforme un travail de O(n·k) en O(n).

Quelle est la complexité temporelle du sous-tableau de somme maximale de taille k ?

Avec une fenêtre glissante, la complexité temporelle est de O(n) et l’espace supplémentaire est de O(1) : un parcours pour calculer la somme de la première fenêtre, puis une addition et une soustraction à chaque étape. Additionner séparément chaque fenêtre nécessite (n-k+1) × k additions, soit O(n·k), environ 2.5 × 10^7 pour n = 10^4 et k = 5000.

En quoi est-ce différent du problème du sous-tableau de somme maximale ?

Ici, la longueur est fixe à k, donc chaque candidat est une fenêtre et une somme glissante les couvre tous. Dans le problème du sous-tableau de somme maximale, la longueur est libre, et il te faut l’algorithme de Kadane, qui décide à chaque élément s’il faut prolonger la séquence actuelle ou en commencer une nouvelle. Une fenêtre fixe n’offre jamais ce choix.

Les sommes préfixes peuvent-elles aussi résoudre ce problème ?

Oui. Construisez prefix[i] comme la somme des i premiers éléments, et la fenêtre commençant à s a pour somme prefix[s+k] - prefix[s]. Cela prend aussi un temps de O(n), mais stocke n+1 totaux. La fenêtre glissante obtient les mêmes sommes avec deux variables.

Python

def maxSumSubarray(nums, k):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

nums = [4, -1, 3, 7, -2, 5, 1]
k = 3

Attendu