Split Array Largest Sum

Q: Quelle est la complexité temporelle du problème « Split Array Largest Sum » ?

La recherche binaire s’exécute en O(n log S) temps, où n est la longueur de nums et S sa somme. Chaque vérification gloutonne parcourt le tableau en un seul passage, et l’intervalle des plafonds est divisé par deux après chaque vérification : environ 29 vérifications lorsque S = 5 × 10^8 . Elle utilise un espace supplémentaire de O(1) . La programmation dynamique prend O(k·n²) en temps et O(n) en espace.

Q: Pourquoi la vérification de faisabilité est-elle monotone ?

Si chaque partie d’un certain découpage a une somme inférieure ou égale à c , ce même découpage a aussi chaque partie inférieure ou égale à c+1 . Ainsi, dès qu’une limite fonctionne, toute limite supérieure fonctionne également, et dès qu’une limite échoue, toute limite inférieure échoue. Les réponses forment une suite de « non » suivie d’une suite de « oui », ce qui est exactement ce dont la recherche binaire a besoin pour trouver la frontière.

Q: Pourquoi la vérification gloutonne trouve-t-elle le plus petit nombre de parties ?

Greedy continue d’ajouter des valeurs à une partie jusqu’à ce que la suivante dépasse le plafond. Comparez-le à toute partition valide, partie par partie. Chaque partie de Greedy commence au même endroit ou après la partie de l’autre partition portant le même numéro ; ses valeurs jusqu’à la fin de cette partie forment donc un morceau d’une partie qui respecte le plafond. Aucune valeur n’est négative, donc le morceau le respecte aussi, et Greedy s’étend au moins aussi loin. Greedy ne prend jamais de retard, donc il couvre le tableau avec aussi peu de parties que n’importe quelle partition.

Q: La recherche binaire fonctionne-t-elle avec des nombres négatifs ?

Non. Avec des valeurs négatives, ajouter une valeur peut réduire une somme : l’algorithme glouton peut donc fermer une partie trop tôt et passer à côté d’une séparation qui fonctionne. Diviser une partie peut aussi augmenter la somme de l’un des morceaux au-delà de celle de la partie entière ; avoir moins de k parties ne signifie donc plus qu’une solution en k parties fonctionne. La programmation dynamique ne fait aucune de ces hypothèses et reste correcte, en O(k·n²) temps.

DifficileRecherche binaire Programmation dynamique

+10

On vous donne un tableau nums d’entiers non négatifs et un entier k. Découpez nums en exactement k parties, chaque partie étant une séquence non vide de valeurs voisines, et en conservant l’ordre des parties. Chaque partie a une somme, et le coût d’un découpage est la plus grande de ces sommes.

Renvoyez le coût minimal qu’un découpage en k parties peut atteindre.

Fonction

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

numsinteger-array: les valeurs non négatives, dans l’ordre
kinteger: le nombre de parties contiguës dans lesquelles les découper
Renvoieinteger: la plus petite valeur possible de la somme de la plus grande partie

Contraintes

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ nums.length
Chaque partie contient au moins une valeur. Une partie dont toutes les valeurs sont égales à 0 a une somme de 0, ce qui est autorisé.

Exemples

Entrée: nums = [6, 2, 9, 4, 7, 3]k = 3
Sortie: 13
Explication: La partition [6, 2], [9, 4], [7, 3] a pour sommes 8, 13 et 10, donc son coût est de 13. Aucune partition n’a un coût de 12 : en regroupant les éléments de gauche à droite avec une somme maximale de 12 pour chaque groupe, on obtient [6, 2], [9], [4, 7], [3], soit quatre groupes alors que seuls trois sont autorisés.

Entrée: nums = [8, 1, 1, 1, 5]k = 2
Sortie: 8
Explication: Le 8 se trouve dans une partie, donc aucune séparation ne peut coûter moins de 8. [8] et [1, 1, 1, 5] totalisent tous deux 8, donc 8 est atteint.

+20 tests cachés à la soumission

Pour aller plus loin

Chaque vérification gloutonne lit toutes les valeurs n. Avec des sommes préfixes, une vérification peut plutôt trouver où se termine chaque partie par recherche binaire. Quelle est la rapidité de la méthode complète lorsque k est petit et que nums est long ?

Indices

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

0 sur 3 ouverts

Solution

Les deux exigences se contrarient : tu dois utiliser exactement k parties, et tu veux que la plus grande soit aussi petite que possible. Essayer tous les emplacements des k-1 coupures explose en complexité, et une programmation dynamique sur les préfixes ramène cela à O(k·n²), ce qui reste trop lent pour 5000 valeurs. L’idée rapide consiste à inverser la question. Au lieu de chercher la meilleure partition, on devine une limite et on demande si k parties peuvent la respecter. Un seul parcours glouton répond à cette question, les réponses ne changent qu’une seule fois à mesure que la limite augmente, et une recherche binaire trouve ce changement en environ 29 parcours.

Programmation dynamique sur les préfixes

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Examine la dernière partie d’un découpage. Si les j premières valeurs forment p parties, la dernière partie est une séquence nums[i..j-1], et les i premières valeurs forment les p-1 autres parties. Le coût est le plus grand de deux nombres : le coût de ces p-1 parties et la somme de la dernière séquence. Quelle que soit la dernière séquence, vous voulez découper les i premières valeurs au coût le plus faible possible, et ce découpage optimal ne dépend de rien à sa droite. Vous pouvez donc le calculer une fois et le réutiliser.

Notons best[p][j] le coût minimal pour découper les j premières valeurs en p parties. Pour une seule partie, il n’y a pas de choix : best[1][j] est la somme des j premières valeurs. Pour plus de parties, essayez chaque début i de la dernière partie : best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]), où prefix[j] est la somme des j premières valeurs. Le début i va de p-1, car p-1 parties non vides nécessitent au moins p-1 valeurs, jusqu’à j-1, car la dernière partie doit contenir une valeur. La réponse est best[k][n]. La ligne p ne lit que la ligne p-1, donc deux lignes de longueur n+1 suffisent.

Dans le premier exemple, découper [6, 2, 9, 4] en deux parties peut faire se terminer la première partie après 6 (coût max(6, 15) = 15), après 2 (max(8, 13) = 13) ou après 9 (max(17, 4) = 17), donc best[2][4] = 13. Ensuite, best[3][6] essaie la dernière partie [7, 3] et obtient max(13, 10) = 13, qu’aucun autre début ne surpasse.

Le problème, c’est le temps de calcul. Il y a k lignes, n fins par ligne et jusqu’à n débuts par fin : jusqu’à k·n²/2 étapes. Avec n = 5000 et k = 2500, la boucle interne s’exécute environ 1.8 × 10^10 fois : 18 secondes, même à 10^9 étapes simples par seconde. Cette programmation dynamique reste utile à connaître : elle ne suppose jamais que les valeurs sont non négatives, et continue donc de fonctionner là où la méthode rapide échoue.

Algorithme

Construis prefix, où prefix[j] est la somme des j premières valeurs.
Définis la ligne pour une seule partie : best[j] = prefix[j].
Pour chaque nombre de parties p de 2 à k, et chaque fin j de p à n, prends le minimum, pour i de p-1 à j-1, de max(best[i], prefix[j] - prefix[i]).
Stocke ces minimums dans une nouvelle ligne et fais-en best.
Renvoie best[n].

def splitArray(nums, k):
    n = len(nums)
    # prefix[j] is the sum of the first j values
    prefix = [0] * (n + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x
    # best[j]: the smallest largest part when the first j values form one part
    best = prefix[:]
    for parts in range(2, k + 1):
        nxt = [0] * (n + 1)
        for j in range(parts, n + 1):
            lowest = prefix[j]  # never worse than one part holding everything
            for i in range(parts - 1, j):
                # the first i values form parts-1 parts, nums[i..j-1] is the last part
                worst = max(best[i], prefix[j] - prefix[i])
                if worst < lowest:
                    lowest = worst
            nxt[j] = lowest
        best = nxt
    return best[n]

Recherche binaire sur la somme maximale

Intuition

Inversez la question. Choisissez un plafond c et demandez-vous : peut-on découper nums en k parties dont la somme de chacune est au plus c ? La réponse au problème est le plus petit plafond pour lequel la réponse est oui. Cette question est beaucoup plus simple que le problème initial, pour deux raisons.

Premièrement, un seul parcours glouton suffit pour y répondre. Parcourez les valeurs de gauche à droite et continuez à ajouter des valeurs à la partie actuelle tant que sa somme ne dépasse pas c ; lorsque la valeur suivante ferait dépasser c, clôturez la partie et commencez-en une nouvelle avec cette valeur. Cette méthode utilise le moins de parties possible parmi tous les découpages respectant le plafond. Comparez-la à n’importe quel autre découpage valide, partie par partie. Les deux premières parties commencent à la première valeur, et l’algorithme glouton ne s’arrête que lorsque la valeur suivante ne tient pas ; sa première partie se termine donc au moins aussi loin à droite. La deuxième partie gloutonne commence alors au même endroit ou plus loin que l’autre deuxième partie. Les valeurs qu’elle contient jusqu’à la fin de cette partie en constituent un sous-ensemble et, puisqu’il n’y a pas de valeurs négatives, un sous-ensemble n’a jamais une somme supérieure à celle de l’ensemble ; ces valeurs tiennent donc, et l’algorithme glouton va de nouveau au moins aussi loin. Il ne prend jamais de retard, et n’a donc jamais besoin de plus de parties.

Deuxièmement, avoir moins de k parties revient au même qu’en avoir exactement k. Si l’algorithme glouton a besoin de m < k parties, découpez en deux une partie qui contient deux valeurs ou plus. La somme de ses sous-parties ne dépasse pas celle de la partie entière, car aucune valeur n’est négative, et puisque n ≥ k, il y a toujours une telle partie jusqu’à ce que vous atteigniez k. Le test est donc partsNeeded(c) ≤ k.

Voici maintenant la propriété clé : le test est monotone. Si le plafond c convient, c+1 convient aussi, puisque le même découpage respecte toujours un plafond plus élevé. Pour les plafonds allant de max(nums) à sum(nums), les réponses sont non, non, ..., non, oui, oui, ..., oui, et vous cherchez le premier oui. Les bornes de l’intervalle sont sûres : aucun plafond inférieur à max(nums) ne peut contenir cette valeur, et le total tient toujours dans une seule partie. Le premier oui correspond aussi à un coût réel, et pas seulement à une borne : si aucune partie de son découpage n’avait une somme exactement égale à c, le plafond c-1 conviendrait aussi.

Suivez le premier exemple, [6, 2, 9, 4, 7, 3] avec k = 3. Les plafonds vont de 9 à 31. Avec un plafond de 20, on obtient [6, 2, 9], [4, 7, 3] : 2 parties, oui, l’intervalle devient donc 9 à 20. Avec un plafond de 14, on obtient [6, 2], [9, 4], [7, 3] : 3 parties, oui, l’intervalle est de 9 à 14. Avec un plafond de 11, on obtient [6, 2], [9], [4, 7], [3] : 4 parties, non, l’intervalle devient 12 à 14. Avec un plafond de 13, il faut 3 parties, oui, l’intervalle est de 12 à 13. Avec un plafond de 12, il en faut 4, non ; la réponse est donc 13.

Chaque parcours lit n valeurs et l’intervalle est divisé par deux à chaque fois. Avec un total S pouvant atteindre 5 × 10^8, cela représente environ 29 parcours de 5000 valeurs, soit environ 150000 étapes.

Algorithme

Définissez lo = max(nums) et hi = sum(nums).
Tant que lo < hi, prenez mid = lo + (hi - lo) / 2.
Comptez les parties dont l’algorithme glouton a besoin avec la limite mid : commencez avec 1 partie et une somme cumulée de 0 ; lorsque l’ajout d’une valeur ferait dépasser mid, ajoutez une partie et recommencez la somme à cette valeur.
Si le nombre est inférieur ou égal à k, définissez hi = mid ; sinon, définissez lo = mid + 1.
Retournez lo.

def splitArray(nums, k):
    def parts_needed(cap):
        # Fill each part left to right and start a new one only when the next value would pass cap.
        parts, current = 1, 0
        for x in nums:
            if current + x > cap:
                parts += 1
                current = x
            else:
                current += x
        return parts

    lo, hi = max(nums), sum(nums)  # one value per part at best, everything in one part at worst
    while lo < hi:
        mid = (lo + hi) // 2
        if parts_needed(mid) <= k:
            hi = mid  # mid works, so the answer is mid or smaller
        else:
            lo = mid + 1  # mid needs more than k parts, so the answer is larger
    return lo

Pièges et cas limites

La recherche est courte ; les bogues se trouvent donc dans le test glouton et dans les bornes.

Initialiser lo en dessous de max(nums). Le test glouton place une valeur supérieure à la limite dans une partie à elle seule, puis continue ; il considère donc qu’une limite de 5 convient pour [1, 9] avec k = 2. Commence à la valeur maximale, ou fais échouer le test lorsqu’une valeur dépasse la limite.
Tester partsNeeded(c) == k. L’algorithme glouton a souvent besoin de moins de parties que k : pour [3, 0, 4] et k = 3, une limite de 4 regroupe [3, 0] et [4]. Avec ==, aucune limite ne convient. On peut toujours subdiviser les parties lorsqu’il y en a moins ; teste donc ≤ k.
Compter les parties à partir de 0. La première partie existe avant que toute valeur ne la fasse déborder, donc le compteur commence à 1.
Définir hi = mid - 1 lorsque mid convient. Cela peut éliminer la réponse elle-même. Garde hi = mid et boucle tant que lo < hi.
Initialiser le i de la programmation dynamique à 0. Une cellule best[i] avec i < p-1 correspond à moins de valeurs que de parties, ce qu’aucun découpage ne peut produire ; dans une ligne remplie de zéros, elle indique un coût de 0. Pour [100, 1, 1] avec k = 3, la programmation dynamique renvoie alors 2 au lieu de 100. Commence i à p-1.
Dépassement de capacité pour des limites plus élevées. Ici, le total est au plus 5 × 10^8, donc les entiers de 32 bits suffisent. Si les valeurs atteignent 10^6, 2148 d’entre elles suffisent déjà à dépasser 2^31-1 ; utilise donc des sommes sur 64 bits.

Questions fréquentes4

Quelle est la complexité temporelle du problème « Split Array Largest Sum » ?

La recherche binaire s’exécute en O(n log S) temps, où n est la longueur de nums et S sa somme. Chaque vérification gloutonne parcourt le tableau en un seul passage, et l’intervalle des plafonds est divisé par deux après chaque vérification : environ 29 vérifications lorsque S = 5 × 10^8. Elle utilise un espace supplémentaire de O(1). La programmation dynamique prend O(k·n²) en temps et O(n) en espace.

Pourquoi la vérification de faisabilité est-elle monotone ?

Si chaque partie d’un certain découpage a une somme inférieure ou égale à c, ce même découpage a aussi chaque partie inférieure ou égale à c+1. Ainsi, dès qu’une limite fonctionne, toute limite supérieure fonctionne également, et dès qu’une limite échoue, toute limite inférieure échoue. Les réponses forment une suite de « non » suivie d’une suite de « oui », ce qui est exactement ce dont la recherche binaire a besoin pour trouver la frontière.

Pourquoi la vérification gloutonne trouve-t-elle le plus petit nombre de parties ?

Greedy continue d’ajouter des valeurs à une partie jusqu’à ce que la suivante dépasse le plafond. Comparez-le à toute partition valide, partie par partie. Chaque partie de Greedy commence au même endroit ou après la partie de l’autre partition portant le même numéro ; ses valeurs jusqu’à la fin de cette partie forment donc un morceau d’une partie qui respecte le plafond. Aucune valeur n’est négative, donc le morceau le respecte aussi, et Greedy s’étend au moins aussi loin. Greedy ne prend jamais de retard, donc il couvre le tableau avec aussi peu de parties que n’importe quelle partition.

La recherche binaire fonctionne-t-elle avec des nombres négatifs ?

Non. Avec des valeurs négatives, ajouter une valeur peut réduire une somme : l’algorithme glouton peut donc fermer une partie trop tôt et passer à côté d’une séparation qui fonctionne. Diviser une partie peut aussi augmenter la somme de l’un des morceaux au-delà de celle de la partie entière ; avoir moins de k parties ne signifie donc plus qu’une solution en k parties fonctionne. La programmation dynamique ne fait aucune de ces hypothèses et reste correcte, en O(k·n²) temps.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

nums = [6, 2, 9, 4, 7, 3]
k = 3

Attendu