Maximum Sum Subarray of Size K

Q: ¿Qué es una ventana deslizante de tamaño fijo?

Es un rango de exactamente k elementos contiguos que avanza un paso a la vez a través de un array. En lugar de volver a calcular el rango desde cero en cada posición, actualizas un valor acumulado: sumas el elemento que entra por la derecha y quitas el que sale por la izquierda. Eso convierte un trabajo de O(n·k) en O(n) .

Q: ¿Cuál es la complejidad temporal del subarreglo de suma máxima de tamaño k?

Con una ventana deslizante, el tiempo es O(n) y el espacio adicional es O(1) : una pasada para sumar la primera ventana y, después, una suma y una resta por paso. Sumar cada ventana por separado cuesta (n-k+1) × k sumas, lo que es O(n·k) , aproximadamente 2.5 × 10^7 para n = 10^4 y k = 5000 .

Q: ¿En qué se diferencia esto del problema del subarreglo máximo?

Aquí la longitud está fija en k , así que cada candidato es una ventana y una suma deslizante las cubre todas. En el problema de la submatriz de suma máxima, la longitud es libre y necesitas el algoritmo de Kadane, que decide en cada elemento si extiende la secuencia actual o empieza una nueva. Una ventana fija nunca tiene esa opción.

Q: ¿También se puede resolver con sumas de prefijos?

Sí. Construye prefix[i] como la suma de los primeros i elementos, y la ventana que empieza en s suma prefix[s+k] - prefix[s] . Eso también requiere tiempo O(n) , pero almacena n+1 totales. La ventana deslizante obtiene las mismas sumas con dos variables.

FácilVentana deslizante

+10

Recibes un array de números enteros nums y una longitud de ventana k. Examina cada secuencia de exactamente k elementos contiguos y devuelve la suma más grande entre ellas. Los valores pueden ser negativos, así que la respuesta también puede ser negativa.

Función

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

numsinteger-array: el arreglo de enteros
kinteger: cuántos elementos vecinos contiene cada ventana
Devuelveinteger: la suma más grande de cualesquiera k elementos consecutivos

Restricciones

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

Ejemplos

Entrada: nums = [4, -1, 3, 7, -2, 5, 1]k = 3
Salida: 10
Explicación: Las cinco ventanas de longitud 3 suman 6, 9, 8, 10 y 4. La mayor es 7 + (-2) + 5 = 10.

Entrada: nums = [-3, -8, -1, -6]k = 2
Salida: -7
Explicación: Todos los valores son negativos, así que todas las sumas de ventanas también lo son: -11, -9 y -7. La mayor de ellas es -1 + (-6) = -7.

Entrada: nums = [5, -2, 4]k = 3
Salida: 7
Explicación: Cuando k es igual a la longitud del array, hay una ventana, el array completo, y 5 + (-2) + 4 = 7.

+15 pruebas ocultas al enviar

Para ir más allá

¿También puedes devolver dónde comienza la mejor ventana, eligiendo la que está más a la izquierda cuando varias ventanas empatan?

Pistas

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

0 de 3 abiertas

Solución

Hay n-k+1 ventanas, y sumar cada una desde cero cuesta k sumas. El truco es que dos ventanas vecinas se superponen en todos menos dos elementos. Desliza la ventana en lugar de reconstruirla: un valor entra, otro sale, y cada suma de ventana cuesta dos operaciones.

Suma todas las ventanas

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

Intuición

Una ventana queda determinada por dónde empieza. Puede empezar en el índice 0, 1 y así sucesivamente hasta n-k, porque un inicio posterior se saldría del final del arreglo. Para cada inicio, suma los k elementos y compara el total con el mejor hasta el momento.

Para [4, -1, 3, 7, -2, 5, 1] y k = 3, eso da las sumas 6, 9, 8, 10, 4, y la respuesta es 10. Inicializa el mejor con la suma de la primera ventana o con el entero más pequeño, nunca con 0: si todos los valores son negativos, 0 sería mayor que todas las ventanas reales.

El costo es de (n-k+1) × k sumas. Alcanza su máximo cuando k es aproximadamente la mitad de n: con n = 10^4 y k = 5000, son 5001 × 5000, alrededor de 2.5 × 10^7 sumas, y casi todas repiten el trabajo hecho para la ventana anterior.

Algoritmo

Establece best en el valor más pequeño posible.
Para cada inicio desde 0 hasta n-k, establece total = 0.
Suma nums[start] hasta nums[start+k-1] a total.
Si total supera a best, guárdalo.
Devuelve 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

Desliza una ventana fija

Intuición

Compara la ventana que empieza en el índice 0 con la que empieza en el índice 1. En [4, -1, 3, 7, -2, 5, 1] con k = 3, son 4 + (-1) + 3 = 6 y (-1) + 3 + 7 = 9. Ambas contienen -1 y 3. La segunda suma es la primera más el valor que entró, 7, menos el valor que salió, 4: 6 + 7 - 4 = 9.

Esto se cumple en cada paso. Cuando el extremo derecho de la ventana se mueve al índice i, el elemento en i entra y el elemento en i-k sale. Así que sumas la primera ventana una vez y luego actualizas la suma con una suma y una resta por paso. Las sumas son 6, 9, 8, 10, 4, las mismas que con la fuerza bruta, y te quedas con la mayor.

Cada elemento entra una vez y sale como máximo una vez, así que el tiempo es O(n). Mantienes dos números, la suma de la ventana actual y la mejor, así que el espacio adicional es O(1). Ninguna suma supera 10^4 × 10^4 = 10^8, así que basta con un entero de 32 bits.

Algoritmo

Suma nums[0] hasta nums[k-1] en window.
Asigna best = window.
Para cada i desde k hasta n-1, suma nums[i] y resta nums[i-k].
Después de cada paso, asigna a best el mayor valor entre best y window.
Devuelve 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

Errores comunes y casos límite

La idea de la ventana es sencilla, así que los errores se esconden en los valores iniciales y los índices.

Iniciar best en 0. Con [-3, -8, -1, -6] y k = 2, la respuesta real es -7, pero nunca se obtiene un valor de best menor que 0, que termina siendo la respuesta.
Restar el elemento equivocado. Cuando entra nums[i], el elemento que sale es nums[i-k]. Usar nums[i-k+1] o nums[i-k-1] produce ventanas de longitud incorrecta.
Detener el recorrido de fuerza bruta un inicio antes de tiempo. La última ventana empieza en n-k, así que el bucle debe incluirla. Si k = n, esa es la única ventana, y un error de desfase hace que no se compruebe ninguna ventana y se devuelva el valor inicial de best.
Comparar solo después del bucle. La mejor ventana puede ser la primera, así que compara también la primera suma o inicializa best con ella.
Olvidar que R y Lua cuentan desde 1. La primera ventana es nums[1..k], y el elemento que sale cuando entra nums[i] sigue siendo nums[i-k].

Preguntas frecuentes4

¿Qué es una ventana deslizante de tamaño fijo?

Es un rango de exactamente k elementos contiguos que avanza un paso a la vez a través de un array. En lugar de volver a calcular el rango desde cero en cada posición, actualizas un valor acumulado: sumas el elemento que entra por la derecha y quitas el que sale por la izquierda. Eso convierte un trabajo de O(n·k) en O(n).

¿Cuál es la complejidad temporal del subarreglo de suma máxima de tamaño k?

Con una ventana deslizante, el tiempo es O(n) y el espacio adicional es O(1): una pasada para sumar la primera ventana y, después, una suma y una resta por paso. Sumar cada ventana por separado cuesta (n-k+1) × k sumas, lo que es O(n·k), aproximadamente 2.5 × 10^7 para n = 10^4 y k = 5000.

¿En qué se diferencia esto del problema del subarreglo máximo?

Aquí la longitud está fija en k, así que cada candidato es una ventana y una suma deslizante las cubre todas. En el problema de la submatriz de suma máxima, la longitud es libre y necesitas el algoritmo de Kadane, que decide en cada elemento si extiende la secuencia actual o empieza una nueva. Una ventana fija nunca tiene esa opción.

¿También se puede resolver con sumas de prefijos?

Sí. Construye prefix[i] como la suma de los primeros i elementos, y la ventana que empieza en s suma prefix[s+k] - prefix[s]. Eso también requiere tiempo O(n), pero almacena n+1 totales. La ventana deslizante obtiene las mismas sumas con dos variables.

Python

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

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado