Split Array Largest Sum

Q: Quelle est la complexité temporelle de Split Array Largest Sum ?

Un temps de O(n log S) et un espace supplémentaire de O(1) , où S est la somme de nums : chaque vérification gloutonne effectue un seul parcours, et l’intervalle des plafonds est divisé par deux après chaque vérification. Cela représente environ 29 vérifications lorsque S = 5 × 10^8 . La programmation dynamique prend un temps de O(k·n²) .

Q: Pourquoi le test de faisabilité est-il monotone ?

Si chaque partie d’un découpage a une somme inférieure ou égale à c , le même découpage respecte la limite c+1 . Ainsi, dès qu’une limite fonctionne, toutes les limites supérieures fonctionnent, et les réponses forment une suite de « non » suivie d’une suite de « oui ». La recherche binaire trouve le premier « oui ».

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

Non. Une valeur négative peut réduire une somme, donc l’algorithme glouton peut fermer une partie trop tôt, et diviser une partie peut faire dépasser à un morceau la somme totale. La programmation dynamique ne fait aucune de ces hypothèses et reste correcte.

DifficileRecherche binaire Programmation dynamique

+10

Vous obtenez un tableau nums d’entiers non négatifs et un entier k. Découpez nums en exactement k parties, chacune étant une séquence non vide de valeurs voisines et les parties conservant leur ordre. 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 égale à 0, ce qui est autorisé.

Exemples

Entrée: nums = [6, 2, 9, 4, 7, 3]k = 3
Sortie: 13
Explication: La division en [6, 2], [9, 4], [7, 3] coûte 13. Aucune division ne coûte 12 : en regroupant les éléments de gauche à droite sans dépasser 12, on obtient [6, 2], [9], [4, 7], [3], soit quatre éléments.

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.

Pour aller plus loin

Avec des sommes préfixes, une vérification gloutonne peut trouver où chaque partie se termine par recherche binaire. À quelle vitesse l’ensemble de la méthode s’exécute-t-il lorsque k est petit ?

Indices

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

0 sur 3 ouverts

Solution

Rechercher directement la meilleure séparation coûte O(k·n²), même avec la programmation dynamique. Inversez la question : peut-on maintenir k parties sous une limite donnée ? Un seul parcours glouton permet d’y répondre ; la réponse passe de non à oui une seule fois lorsque la limite augmente, et la recherche binaire trouve ce seuil.

Programmation dynamique sur les préfixes

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Écris best[p][j] pour désigner le coût minimal pour découper les j premières valeurs en p parties. Si la dernière partie est nums[i..j-1], le coût est le maximum entre best[p-1][i] et la somme de cette partie, et la meilleure partition des i premières valeurs ne dépend de rien situé à sa droite. Ainsi, best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]), avec i allant de p-1 à j-1, afin que chaque partie contienne une valeur. La ligne p ne lit que la ligne p-1, donc deux lignes suffisent.

L'algorithme s'exécute en jusqu'à k·n²/2 étapes : environ 1.8 × 10^10 pour n = 5000 et k = 2500.

Algorithme

Construisez prefix, où prefix[j] est la somme des j premières valeurs, et définissez best[j] = prefix[j] pour une seule partie.
Pour chaque nombre de parties p de 2 à k, et chaque fin j de p à n, prenez le minimum de max(best[i], prefix[j] - prefix[i]) pour i de p-1 à j-1.
Stockez ces minimums dans une nouvelle ligne et faites-en best.
Renvoyez 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

Pour tester une capacité c, parcourez les valeurs de gauche à droite et ajoutez-les à la partie en cours tant que sa somme ne dépasse pas c, puis commencez une nouvelle partie. Cette méthode utilise le moins de parties possible. Par rapport à toute partition valide, la première partie de l’algorithme glouton se termine au moins aussi loin à droite, donc sa partie suivante commence au même endroit ou plus loin que celle de l’autre partition. Les valeurs qu’il prend jusqu’à la fin de cette partie forment un morceau d’une partie dont la somme ne dépasse pas la capacité et, comme aucune valeur n’est négative, la somme d’un morceau ne dépasse jamais celle de l’ensemble. L’algorithme glouton ne prend donc jamais de retard.

Avoir moins de k parties est aussi bien qu’en avoir k : diviser en deux une partie contenant au moins deux valeurs n’augmente jamais une somme. Le test est donc partsNeeded(c) ≤ k.

Effectuez une recherche binaire pour trouver la plus petite capacité qui satisfait le test, entre max(nums), puisque cette valeur se trouve dans une partie, et sum(nums), qui tient toujours dans une seule partie.

Algorithme

Définissez lo = max(nums) et hi = sum(nums).
Tant que lo < hi, prenez mid = lo + (hi - lo) / 2.
Comptez les segments gloutons sous mid : commencez avec 1 segment dont la somme vaut 0 ; lorsque l’ajout d’une valeur ferait dépasser mid, ajoutez un segment et recommencez la somme avec cette valeur.
Si le nombre est inférieur ou égal à k, définissez hi = mid ; sinon, définissez lo = mid + 1.
Renvoyez 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

Initialiser lo à une valeur inférieure à max(nums). L’algorithme glouton place une valeur supérieure à la limite dans une partie à elle seule ; il indique donc que la limite 5 convient pour [1, 9] avec k = 2.
Tester partsNeeded(c) == k. Pour [3, 0, 4] et k = 3, la limite 4 regroupe [3, 0] et [4] ; aucune limite ne convient donc jamais.
Compter les parties à partir de 0, ce qui rend chaque décompte trop petit d’une unité.
Définir hi = mid - 1 lorsque mid convient, ce qui fait perdre la réponse lorsqu’elle est égale à mid.
Initialiser i de la programmation dynamique à 0. Une cellule contenant moins de valeurs que de parties est interprétée comme ayant un coût de 0 ; avec [100, 1, 1] et k = 3, le résultat indiqué est 2 au lieu de 100.

Questions fréquentes3

Quelle est la complexité temporelle de Split Array Largest Sum ?

Un temps de O(n log S) et un espace supplémentaire de O(1), où S est la somme de nums : chaque vérification gloutonne effectue un seul parcours, et l’intervalle des plafonds est divisé par deux après chaque vérification. Cela représente environ 29 vérifications lorsque S = 5 × 10^8. La programmation dynamique prend un temps de O(k·n²).

Pourquoi le test de faisabilité est-il monotone ?

Si chaque partie d’un découpage a une somme inférieure ou égale à c, le même découpage respecte la limite c+1. Ainsi, dès qu’une limite fonctionne, toutes les limites supérieures fonctionnent, et les réponses forment une suite de « non » suivie d’une suite de « oui ». La recherche binaire trouve le premier « oui ».

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

Non. Une valeur négative peut réduire une somme, donc l’algorithme glouton peut fermer une partie trop tôt, et diviser une partie peut faire dépasser à un morceau la somme totale. La programmation dynamique ne fait aucune de ces hypothèses et reste correcte.

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

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu