Split Array Largest Sum
Recibes un arreglo nums de enteros no negativos y un entero k. Divide nums en exactamente k partes, donde cada parte es un tramo no vacío de valores contiguos y las partes conservan su orden. Cada parte tiene una suma, y el costo de una división es la mayor de esas sumas.
Devuelve el menor costo que se puede alcanzar con cualquier división en k partes.
Función
- numsinteger-array
- los valores no negativos, en orden
- kinteger
- la cantidad de partes contiguas en las que cortarlos
- Devuelveinteger
- el menor valor posible de la suma de la parte más grande
Restricciones
1 ≤ nums.length ≤ 50000 ≤ nums[i] ≤ 1051 ≤ k ≤ nums.length- Cada parte contiene al menos un valor. Una parte cuyos valores son todos 0 suma 0, lo cual está permitido.
Ejemplos
- Entrada
- nums = [6, 2, 9, 4, 7, 3]k = 3
- Salida
- 13
- Explicación
- La división
[6, 2],[9, 4],[7, 3]cuesta 13. Ninguna división cuesta 12: al empaquetar las partes de izquierda a derecha con un límite de 12, se obtiene[6, 2],[9],[4, 7],[3], cuatro partes.
- Entrada
- nums = [8, 1, 1, 1, 5]k = 2
- Salida
- 8
- Explicación
- El 8 está en alguna parte, así que ninguna división puede costar menos de 8.
[8]y[1, 1, 1, 5]suman 8.
- Entrada
- nums = [3, 0, 4]k = 3
- Salida
- 4
- Explicación
- Tres valores y tres partes dejan un valor por parte, con sumas de 3, 0 y 4. Se permite que una parte sume 0.
Para ir más allá
Con sumas de prefijos, una comprobación voraz puede encontrar dónde termina cada parte mediante búsqueda binaria. ¿Qué tan rápido se vuelve todo el método cuando k es pequeño?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Supón que alguien promete que la parte más grande puede sumar como máximo
c. ¿Puedes decidir rápidamente sikpartes son suficientes?Rellena las partes de izquierda a derecha y cierra una parte solo cuando el siguiente valor haga que supere
c. Así se usan menos partes, y un valor mayor decnunca requiere más.Búsqueda binaria de
centre el valor más grande y la suma total. Si el recuento voraz es como máximok, la respuesta esco menor; de lo contrario, es mayor.
Solución
Buscar directamente la mejor división cuesta O(k·n²), incluso con programación dinámica. Plantea la pregunta al revés: ¿pueden mantenerse k partes por debajo de un límite dado? Una pasada codiciosa responde a eso; la respuesta cambia de no a sí una sola vez a medida que aumenta el límite, y la búsqueda binaria encuentra ese cambio.
Programación dinámica sobre prefijos
Correcto, pero no termina con las pruebas más grandes
Intuición
Escribe best[p][j] para indicar el costo mínimo de dividir los primeros j valores en p partes. Si la última parte es nums[i..j-1], el costo es el mayor entre best[p-1][i] y la suma de esa parte, y la mejor división de los primeros i valores no depende de nada que esté a su derecha. Así que best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]), con i desde p-1 hasta j-1, de modo que cada parte contenga un valor. La fila p solo lee la fila p-1, así que bastan dos filas.
Se ejecuta en hasta k·n²/2 pasos: unos 1.8 × 10^10 para n = 5000 y k = 2500.
Algoritmo
- Construye
prefix, dondeprefix[j]es la suma de los primerosjvalores, y establecebest[j] = prefix[j]para una parte. - Para cada cantidad de partes
pdesde 2 hastak, y cada finaljdesdephastan, toma el mínimo demax(best[i], prefix[j] - prefix[i])paraidesdep-1hastaj-1. - Guarda esos mínimos en una nueva fila y conviértela en
best. - Devuelve
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]Búsqueda binaria sobre la suma más grande
Intuición
Para probar un límite c, recorre de izquierda a derecha y añade valores a la parte actual mientras su suma no supere c; después, empieza una nueva parte. Así se usa el menor número posible de partes. Frente a cualquier partición válida, la primera parte del algoritmo voraz termina al menos igual de a la derecha, por lo que su siguiente parte empieza en el mismo lugar o más adelante que la otra. Sus valores hasta el final de esa parte forman un fragmento de una parte que cabe, y, como no hay valores negativos, un fragmento nunca suma más que el total. Así que el algoritmo voraz nunca se queda atrás.
Menos de k partes es igual de bueno que k: dividir en dos una parte de dos o más valores nunca aumenta una suma. Por tanto, la prueba es partsNeeded(c) ≤ k.
Busca mediante búsqueda binaria el límite más pequeño que pase la prueba, entre max(nums), ya que ese valor forma parte de alguna parte, y sum(nums), que siempre cabe en una sola parte.
Algoritmo
- Establece
lo = max(nums)yhi = sum(nums). - Mientras
lo < hi, tomamid = lo + (hi - lo) / 2. - Cuenta las partes voraces con
mid: empieza con 1 parte y suma 0; cuando agregar un valor haría que se superaramid, agrega una parte y reinicia la suma con ese valor. - Si el recuento es como máximo
k, establecehi = mid; de lo contrario, establecelo = mid + 1. - Devuelve
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
Errores comunes y casos límite
- Empezar con
lopor debajo demax(nums). El algoritmo voraz coloca un valor mayor que el límite en una parte propia, así que indica que el límite 5 es válido para[1, 9]conk = 2. - Comprobar
partsNeeded(c) == k. Para[3, 0, 4]yk = 3, el límite 4 agrupa[3, 0],[4], así que ningún límite pasa la prueba. - Contar las partes desde 0, lo que hace que cada recuento sea una unidad menor.
- Establecer
hi = mid - 1cuandomidfunciona, lo que hace perder la respuesta cuando esmid. - Empezar la
ide la DP en 0. Una celda con menos valores que partes se interpreta como costo 0, y con[100, 1, 1]yk = 3se obtiene 2 en lugar de 100.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de «Split Array Largest Sum»?
Tiempo O(n log S) y espacio adicional O(1), donde S es la suma de nums: cada comprobación voraz es un recorrido, y el rango de los límites se reduce a la mitad después de cada comprobación. Eso equivale a unas 29 comprobaciones cuando S = 5 × 10^8. La programación dinámica toma un tiempo de O(k·n²).
¿Por qué es monótona la comprobación de viabilidad?
Si cada parte de una partición suma como máximo c, la misma partición cabe bajo c+1. Así que, una vez que un límite funciona, todos los límites mayores también funcionan, y las respuestas forman una secuencia de no seguida de una secuencia de sí. La búsqueda binaria encuentra el primer sí.
¿La búsqueda binaria funciona con números negativos?
No. Un valor negativo puede reducir una suma, por lo que el algoritmo voraz podría cerrar una parte demasiado pronto, y dividir una parte puede hacer que un fragmento supere al conjunto. La programación dinámica no hace ninguna de esas suposiciones y sigue siendo correcta.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def splitArray(nums, k):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
nums = [6, 2, 9, 4, 7, 3] k = 3
Salida Esperada
13