Prompt y contexto
Dado un arreglo de enteros de longitud n cuyo final se conecta con su inicio, un subarreglo contiguo puede envolverse (hacer wrap around), pero no puede usar una misma posición dos veces. Devuelve la suma máxima de un subarreglo no vacío. Los entrevistadores suelen pedir a los candidatos que deriven la variante circular a partir del algoritmo de Kadane y expliquen por qué un arreglo de solo números negativos no puede usar a ciegas total - minSum.
Lo que evalúa el entrevistador
- Dividir la respuesta en rangos sin envoltura y con envoltura.
- Usar el complemento entre las sumas de subarreglos máxima y mínima en lugar de duplicar el arreglo.
- Preservar la restricción de subarreglo no vacío para entradas de solo negativos, de un solo elemento y con límites de enteros.
Preguntas de clarificación antes de responder
- ¿El subarreglo debe ser no vacío? Sí, por lo que una entrada de solo números negativos devuelve su valor negativo más grande.
- ¿Se puede usar una posición dos veces? No; un rango con envoltura es el complemento de un rango intermedio no vacío.
- ¿Devolvemos solo la suma o también los límites? Este problema pide la suma; los límites requieren un registro adicional de índices y una representación circular.
Estructura de respuesta en 30 segundos
Divido la respuesta en dos casos. Un rango sin envoltura es la suma máxima ordinaria de un subarreglo. Un rango con envoltura equivale a la suma total menos una suma mínima de subarreglo no vacía. Una sola pasada mantiene las sumas máxima, mínima y total. Si el rango mínimo es el arreglo completo, el complemento está vacío, por lo que devuelvo el máximo ordinario en su lugar. El algoritmo tiene una complejidad de tiempo O(n) y espacio adicional O(1).
Análisis detallado paso a paso
1. Derivar los dos casos
El algoritmo de Kadane encuentra el mejor rango sin envoltura. Un rango con envoltura consta de un sufijo y un prefijo; su complemento es un rango intermedio contiguo no vacío, por lo que su suma es total - minSubarray. Tomar el mayor de estos candidatos cubre todos los rangos válidos.
2. Mantener los invariantes de Kadane
En el valor x, el estado ordinario almacena la mejor suma que termina en la posición actual; el estado mínimo almacena la suma más pequeña que termina allí. Actualiza cada uno a partir del estado actual previo y luego actualiza los extremos globales. Inicializa el máximo global en infinito negativo y el mínimo en infinito positivo para que un arreglo negativo de un solo elemento no se trate como vacío.
3. Manejar entradas con solo números negativos
Cuando todos los valores son negativos, el subarreglo mínimo es el arreglo completo y total - minSubarray es cero, lo que representa un rango vacío y viola el enunciado. Devuelve el máximo ordinario siempre que la mejor suma sea negativa. Rastrear si el rango mínimo cubre todo el arreglo es otra implementación válida, pero la verificación del signo es más simple.
4. Código y complejidad
from typing import List
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
total = 0
current_max = current_min = 0
best_max = float("-inf")
best_min = float("inf")
for value in nums:
total += value
current_max = max(value, current_max + value)
best_max = max(best_max, current_max)
current_min = min(value, current_min + value)
best_min = min(best_min, current_min)
if best_max < 0:
return int(best_max)
return int(max(best_max, total - best_min))Cada elemento se visita una vez: tiempo O(n) y espacio adicional O(1). Usa un tipo de entero más amplio cuando el entero de máquina del lenguaje pueda desbordarse con la suma total o las intermedias.
5. Contraejemplos y verificación
[5,-3,5] tiene una respuesta con envoltura de 5 + 5 = 10. [-3,-2,-3] debe devolver -2, no cero. Para [1,-2,3,-2], la respuesta ordinaria es 3 y el candidato con envoltura no puede superarla. Las pruebas también deben cubrir un solo elemento, entradas de solo positivos, un rango equivalente a todo el arreglo circular y sumas cercanas al límite de los enteros.
Respuesta de muestra de alta calidad
“Primero separo los rangos que cruzan el límite de los que no lo hacen. El caso sin envoltura es el máximo de Kadane. Un rango con envoltura es la suma total del arreglo menos un rango intermedio mínimo no vacío, por lo que mantengo los estados máximo y mínimo de Kadane en una sola pasada. Si todos los valores son negativos, el rango mínimo es todo el arreglo y su complemento está vacío, por lo que devuelvo el máximo ordinario. Esto toma tiempo O(n) y espacio O(1), con pruebas para un solo valor, solo negativos, positivos con envoltura y límites de enteros”.
Errores comunes
- Ejecutar Kadane ordinario en un arreglo duplicado → una posición puede usarse dos veces → acota la ventana o deriva el caso del complemento.
- Devolver siempre
total - minSum→ una entrada de solo negativos produce el rango vacío cero → maneja primero la rama donde el mejor valor es negativo. - Permitir un rango mínimo vacío → la fórmula del complemento pierde la restricción de no vacío → inicia el Kadane mínimo desde un elemento real.
- Afirmar O(n) sin invariantes → la cobertura de los casos límite queda sin demostrar → define ambos casos de rango y cada estado.
Preguntas de seguimiento y respuestas
¿Cómo devolverías las posiciones de inicio y fin?
Registra los límites tanto para el estado máximo como para el mínimo. Una respuesta con envoltura es el complemento del rango mínimo, representado como [minEnd+1,n-1] y [0,minStart-1]; define si la API devuelve dos fragmentos lineales o un inicio circular y su longitud.
¿Cómo cambiaría el código si se permitieran subarreglos vacíos?
La respuesta sería al menos cero, por lo que la suma actual podría reiniciarse en cero. Eso cambia la semántica para arreglos de solo negativos; confirma el enunciado antes de usar una variante de Kadane que permita subarreglos vacíos.
¿Puedes actualizar la respuesta en O(1) para un flujo dinámico de datos?
Agregar elementos en un extremo puede mantener los valores de prefijo, sufijo y resúmenes, pero eliminar un elemento antiguo arbitrario invalida los extremos. Podría necesitarse un segment tree o resúmenes por bloques. Clarifica la dirección de actualización, la frecuencia de consultas y si se permite una aproximación.
¿Qué pasa si el subarreglo debe tener exactamente una longitud k?
La fórmula del complemento ya no se aplica porque la longitud del complemento está restringida. Trata el arreglo como una secuencia de longitud 2n, mantén ventanas de longitud k con sumas de prefijos o una deque, y limita la ventana a n; la complejidad dependerá del patrón de consultas.