Split Array Largest Sum

Q: ¿Cuál es la complejidad temporal de «Split Array Largest Sum»?

La búsqueda binaria se ejecuta en tiempo O(n log S) , donde n es la longitud de nums y S su suma. Cada comprobación voraz recorre el arreglo una vez, y el rango de los límites se reduce a la mitad después de cada comprobación: unas 29 comprobaciones cuando S = 5 × 10^8 . Usa espacio adicional O(1) . La programación dinámica tiene un tiempo de O(k·n²) y un espacio de O(n) .

Q: ¿Por qué es monótona la comprobación de factibilidad?

Si cada parte de alguna partición suma como máximo c , la misma partición también tiene cada parte como máximo c+1 . Así que, una vez que un límite funciona, todos los límites mayores también funcionan; y, una vez que un límite falla, todos los límites menores también fallan. Las respuestas forman una secuencia de «no» seguida de una secuencia de «sí», que es justo lo que necesita la búsqueda binaria para encontrar el límite.

Q: ¿Por qué la comprobación voraz encuentra la menor cantidad de partes?

El algoritmo voraz sigue añadiendo valores a una parte hasta que el siguiente superaría el límite. Compáralo con cualquier partición válida, parte por parte. Cada parte voraz comienza en la misma posición o después que la parte de la otra partición con el mismo número, así que sus valores hasta el final de esa parte forman un segmento de una parte que cabe dentro del límite. Ningún valor es negativo, así que el segmento también cabe, y el algoritmo voraz llega al menos igual de lejos. El algoritmo voraz nunca se queda atrás, así que cubre el arreglo en tan pocas partes como cualquier partición.

Q: ¿La búsqueda binaria funciona con números negativos?

No. Con valores negativos, sumar un valor puede reducir una suma, así que el algoritmo voraz puede cerrar una parte demasiado pronto y pasar por alto una división que sí funciona. Dividir una parte también puede elevar la suma de una de las piezas por encima de la suma total, así que tener menos de k partes ya no significa que k partes funcionen. La programación dinámica no hace ninguna de estas suposiciones y sigue siendo correcta, con un tiempo de O(k·n²) .

DifícilBúsqueda binaria Programación dinámica

+10

Recibes un arreglo nums de enteros no negativos y un entero k. Divide nums en exactamente k partes, donde cada parte es una secuencia no vacía de valores contiguos y las partes mantienen 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 puede alcanzar cualquier división en k partes.

Función

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

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 ≤ 5000
0 ≤ nums[i] ≤ 10⁵
1 ≤ 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] tiene sumas de 8, 13 y 10, así que su costo es 13. Ninguna división tiene un costo de 12: al empaquetar las partes de izquierda a derecha con cada suma como máximo de 12, se obtiene [6, 2], [9], [4, 7], [3], cuatro partes cuando solo se permiten tres.

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, así que se alcanza el 8.

+20 pruebas ocultas al enviar

Para ir más allá

Cada comprobación voraz lee todos los valores de n. Con sumas de prefijos, una comprobación puede encontrar dónde termina cada parte mediante búsqueda binaria. ¿Qué tan rápido se vuelve el método completo cuando k es pequeño y nums es largo?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Las dos exigencias entran en conflicto: debes usar exactamente k partes y quieres que la parte más grande sea lo más pequeña posible. Probar todos los lugares para los k-1 cortes es explosivo, y un programa dinámico sobre prefijos reduce eso a O(k·n²), que sigue siendo demasiado lento para 5000 valores. La idea rápida le da la vuelta a la pregunta. En lugar de buscar la mejor partición, adivina un límite y pregunta si las k partes pueden mantenerse por debajo de él. Una pasada voraz responde a eso; las respuestas solo cambian una vez a medida que aumenta el límite, y la búsqueda binaria encuentra ese cambio en unas 29 pasadas.

Programación dinámica sobre prefijos

Correcto, pero no termina con las pruebas más grandes

Intuición

Observa la última parte de una división. Si los primeros j valores forman p partes, la última parte es algún segmento nums[i..j-1], y los primeros i valores forman las otras p-1 partes. El costo es el mayor de dos números: el costo de esas p-1 partes y la suma del último segmento. Sea cual sea el último segmento, quieres dividir los primeros i valores con el menor costo posible, y esa mejor división no depende de nada a su derecha. Así que puedes calcularla una vez y reutilizarla.

Escribe best[p][j] para el costo mínimo de dividir los primeros j valores en p partes. Con una parte no hay elección: best[1][j] es la suma de los primeros j valores. Para más partes, prueba cada inicio i de la última parte: best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]), donde prefix[j] es la suma de los primeros j valores. El inicio i va desde p-1, porque p-1 partes no vacías necesitan al menos p-1 valores, hasta j-1, porque la última parte necesita un valor. La respuesta es best[k][n]. La fila p solo lee la fila p-1, así que bastan dos filas de longitud n+1.

En el primer ejemplo, dividir [6, 2, 9, 4] en dos partes puede terminar la primera parte después de 6 (costo max(6, 15) = 15), después de 2 (max(8, 13) = 13) o después de 9 (max(17, 4) = 17), así que best[2][4] = 13. Después, best[3][6] prueba con la última parte [7, 3] y obtiene max(13, 10) = 13, que ningún otro inicio mejora.

El problema es la cantidad de trabajo. Hay k filas, n finales por fila y hasta n inicios por final: hasta k·n²/2 pasos. Con n = 5000 y k = 2500, el bucle interno se ejecuta unas 1.8 × 10^10 veces: 18 segundos incluso a 10^9 pasos simples por segundo. Aun así, vale la pena conocer la DP: nunca supone que los valores sean no negativos, así que sigue funcionando cuando el método rápido no lo hace.

Algoritmo

Construye prefix, donde prefix[j] es la suma de los primeros j valores.
Establece la fila para una parte: best[j] = prefix[j].
Para cada cantidad de partes p desde 2 hasta k, y cada extremo j desde p hasta n, toma el mínimo para i desde p-1 hasta j-1 de max(best[i], prefix[j] - prefix[i]).
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 de la suma máxima

Intuición

Plantea la pregunta al revés. Elige un límite c y pregunta: ¿se puede dividir nums en k partes de modo que la suma de cada parte sea como máximo c? La respuesta al problema es el límite más pequeño para el que la respuesta es sí. Esa pregunta es mucho más fácil que la original, por dos motivos.

Primero, basta con una pasada voraz para responderla. Recorre de izquierda a derecha y sigue añadiendo valores a la parte actual mientras su suma no supere c; cuando el siguiente valor haría que lo superara, cierra la parte y empieza una nueva con ese valor. Esto usa la menor cantidad de partes posible en cualquier división que respete el límite. Compárala con cualquier otra división válida, parte por parte. Ambas primeras partes empiezan con el primer valor, y el algoritmo voraz solo se detiene cuando el siguiente valor ya no cabe, así que su primera parte termina al menos igual de lejos. La segunda parte del algoritmo voraz empieza entonces en la misma posición o después que la otra segunda parte. Los valores que contiene hasta el final de esa parte son una porción de ella y, como no hay valores negativos, una porción nunca suma más que el total; por eso caben y el algoritmo voraz vuelve a llegar al menos igual de lejos. El algoritmo voraz nunca se queda atrás, así que nunca necesita más partes.

Segundo, usar menos de k partes es tan válido como usar exactamente k. Si el algoritmo voraz necesita m < k partes, divide en dos una parte que contenga dos o más valores. Sus porciones suman como máximo lo mismo que el total, porque ningún valor es negativo, y como n ≥ k, siempre existe una parte así hasta llegar a k. Por lo tanto, la prueba es partsNeeded(c) ≤ k.

Ahora, la propiedad clave: la prueba es monótona. Si el límite c funciona, c+1 también funciona, ya que la misma división sigue cabiendo con un límite mayor. Para los límites desde max(nums) hasta sum(nums), las respuestas son no, no, ..., no, sí, sí, ..., sí, y quieres encontrar el primer sí. El intervalo es seguro en ambos extremos: ningún límite inferior a max(nums) puede contener ese valor, y el total siempre cabe en una sola parte. El primer sí también es un costo real, no solo un límite: si ninguna parte de la división sumara exactamente c, el límite c-1 también funcionaría.

Recorre el primer ejemplo, [6, 2, 9, 4, 7, 3] con k = 3. Los límites van de 9 a 31. Con el límite 20, se agrupan [6, 2, 9], [4, 7, 3]: 2 partes, sí, así que el intervalo pasa a ser de 9 a 20. Con el límite 14, se obtienen [6, 2], [9, 4], [7, 3]: 3 partes, sí, intervalo de 9 a 14. Con el límite 11, se obtienen [6, 2], [9], [4, 7], [3]: 4 partes, no, intervalo de 12 a 14. Con el límite 13 se necesitan 3 partes, sí, intervalo de 12 a 13. Con el límite 12 se necesitan 4, no, así que la respuesta es 13.

Cada pasada lee n valores y el intervalo se reduce a la mitad cada vez. Con un total S de hasta 5 × 10^8, eso equivale a unas 29 pasadas sobre 5000 valores, aproximadamente 150000 pasos.

Algoritmo

Establece lo = max(nums) y hi = sum(nums).
Mientras lo < hi, toma mid = lo + (hi - lo) / 2.
Cuenta las partes que necesita el algoritmo voraz con el límite mid: empieza con 1 parte y una suma acumulada de 0; cuando añadir un valor superaría mid, añade una parte y reinicia la suma con ese valor.
Si el recuento es como máximo k, establece hi = mid; de lo contrario, establece lo = 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

La búsqueda es breve, así que los errores están en la comprobación voraz y en los límites.

Empezar lo por debajo de max(nums). La comprobación voraz coloca un valor mayor que el límite en una parte propia y continúa, así que considera que un límite de 5 es válido para [1, 9] con k = 2. Empieza por el valor más grande o haz que la comprobación falle cuando un solo valor supere el límite.
Comprobar partsNeeded(c) == k. La estrategia voraz suele necesitar menos partes que k: para [3, 0, 4] y k = 3, el límite 4 agrupa [3, 0], [4]. Con ==, ningún límite pasa la comprobación. Siempre se pueden dividir más las partes cuando hay menos, así que comprueba ≤ k.
Contar las partes desde 0. La primera parte existe antes de que algún valor la desborde, así que el recuento empieza en 1.
Establecer hi = mid - 1 cuando mid funciona. Eso puede omitir la respuesta misma. Mantén hi = mid y repite mientras lo < hi.
Empezar la i de la DP en 0. Una celda best[i] con i < p-1 representa menos valores que partes, algo que ninguna división puede hacer, y en una fila rellenada con ceros se interpreta como un costo de 0. Para [100, 1, 1] con k = 3, la DP informa entonces 2 en lugar de 100. Empieza i en p-1.
Desbordamiento con límites mayores. Aquí el total es como máximo 5 × 10^8, así que los enteros de 32 bits pueden almacenarlo. Si los valores alcanzan 10^6, 2148 de ellos ya superan 2^31-1, así que usa sumas de 64 bits.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de «Split Array Largest Sum»?

La búsqueda binaria se ejecuta en tiempo O(n log S), donde n es la longitud de nums y S su suma. Cada comprobación voraz recorre el arreglo una vez, y el rango de los límites se reduce a la mitad después de cada comprobación: unas 29 comprobaciones cuando S = 5 × 10^8. Usa espacio adicional O(1). La programación dinámica tiene un tiempo de O(k·n²) y un espacio de O(n).

¿Por qué es monótona la comprobación de factibilidad?

Si cada parte de alguna partición suma como máximo c, la misma partición también tiene cada parte como máximo c+1. Así que, una vez que un límite funciona, todos los límites mayores también funcionan; y, una vez que un límite falla, todos los límites menores también fallan. Las respuestas forman una secuencia de «no» seguida de una secuencia de «sí», que es justo lo que necesita la búsqueda binaria para encontrar el límite.

¿Por qué la comprobación voraz encuentra la menor cantidad de partes?

El algoritmo voraz sigue añadiendo valores a una parte hasta que el siguiente superaría el límite. Compáralo con cualquier partición válida, parte por parte. Cada parte voraz comienza en la misma posición o después que la parte de la otra partición con el mismo número, así que sus valores hasta el final de esa parte forman un segmento de una parte que cabe dentro del límite. Ningún valor es negativo, así que el segmento también cabe, y el algoritmo voraz llega al menos igual de lejos. El algoritmo voraz nunca se queda atrás, así que cubre el arreglo en tan pocas partes como cualquier partición.

¿La búsqueda binaria funciona con números negativos?

No. Con valores negativos, sumar un valor puede reducir una suma, así que el algoritmo voraz puede cerrar una parte demasiado pronto y pasar por alto una división que sí funciona. Dividir una parte también puede elevar la suma de una de las piezas por encima de la suma total, así que tener menos de k partes ya no significa que k partes funcionen. La programación dinámica no hace ninguna de estas suposiciones y sigue siendo correcta, con un tiempo de O(k·n²).

Python

def splitArray(nums, k):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado