Domina maximum subarray en entrevista con un guion claro, Kadane paso a paso y casos límite. Practica la respuesta y destaca hoy.
La mayoría de los candidatos que se bloquean en la entrevista sobre maximum subarray no se bloquean porque hayan olvidado el algoritmo. Se bloquean porque nadie les hizo decir la respuesta en voz alta antes de escribir una sola línea de código, y la distancia entre “sé cómo funciona esto” y “puedo explicárselo con claridad a otra persona en tiempo real” es mayor de lo que parece hasta que se sientan frente a un entrevistador.
Esta guía le ofrece un guion breve y repetible: una forma de abrir el problema, derivar la solución óptima a partir de fuerza bruta, hacer un recorrido manual del ejemplo estándar y responder a casi cualquier seguimiento sin sonar como si estuviera recitando un libro de texto. Léala una vez y luego dígala en voz alta. Ese es todo el plan de práctica.
Diga cuál es el problema antes de tocar el código
Por qué la gente tropieza en la primera frase
El error más común al responder un problema de maximum subarray no es equivocarse en el algoritmo: es saltarse por completo la definición del problema y pasar directamente al código. Los entrevistadores lo notan de inmediato. Eso indica que el candidato ha asociado un patrón con una solución memorizada en lugar de razonar de verdad sobre el problema. Y crea una respuesta frágil: en cuanto el entrevistador cambia una restricción, el candidato no tiene a qué aferrarse.
Lo que la mayoría olvida definir es qué significa “contiguous”. Un subarray contiguo es una secuencia de elementos que aparecen consecutivamente en el array original: no puede saltarse elementos ni reordenarlos. La salida es la suma máxima que puede obtenerse con cualquiera de esos subarrays, incluidos los de longitud uno. Según Introduction to Algorithms (CLRS), el problema de maximum subarray se define con precisión en estos términos, y la definición es fundamental: es lo que descarta el enfoque codicioso de “tomar todos los positivos” y lo que hace interesante al problema.
Cómo se ve esto en la práctica
Esta es la introducción de 60 segundos que conviene dar antes de tocar el código:
"La entrada es un array de enteros que puede contener números positivos y negativos. La salida es la suma máxima que podemos obtener de cualquier subarray contiguo; es decir, elegimos un índice inicial y uno final, y sumamos todo lo que hay entre ellos. Podemos escoger un solo elemento, pero no podemos saltarnos elementos ni hacer wrap around. Para el ejemplo [-2, 1, -3, 4, -1, 2, 1, -5, 4], la respuesta es 6, procedente del subarray [4, -1, 2, 1]. Empezaré con el enfoque de fuerza bruta para asegurarme de que tengo el modelo mental correcto y luego veremos una solución más eficiente."
Eso es todo. Cuarenta y cinco segundos, entrada y salida claras, un ejemplo concreto y una hoja de ruta que indica que va a razonar el problema en lugar de recitarlo de memoria. El entrevistador sabe que usted entiende lo que está resolviendo antes de que haya escrito un solo carácter.
Empiece con la fuerza bruta para que la mejor respuesta tenga sentido
La idea de fuerza bruta no es tonta: es el puente
El enfoque de O(n²) tiene mala fama en la preparación para entrevistas, normalmente porque los candidatos lo tratan como un primer borrador vergonzoso por el que tienen que disculparse antes de pasar a la “respuesta real”. Ese marco es incorrecto. La fuerza bruta es útil no porque sea rápida —claramente no lo es—, sino porque vuelve concreto el concepto de suma máxima de subarray. Muestra exactamente qué se está midiendo antes de intentar medirlo de forma eficiente.
La idea de fuerza bruta es simple: para cada índice inicial posible, extienda el subarray un elemento a la vez, manteniendo la suma acumulada y actualizando la mejor suma vista. Dos bucles anidados, sin trucos. El bucle externo elige el inicio y el interno se extiende hasta cada final posible. Usted mantiene un máximo global y lo devuelve al final.
Cómo se ve esto en la práctica
Tome el array [-2, 1, -3, 4, -1]. Empezando en el índice 0: el subarray [-2] da -2, [-2,1] da -1, [-2,1,-3] da -4, [-2,1,-3,4] da 0, [-2,1,-3,4,-1] da -1. Empezando en el índice 1: [1] da 1, [1,-3] da -2, [1,-3,4] da 2, [1,-3,4,-1] da 1. Y así sucesivamente.
Lo que se observa enseguida es que cada vez que se extiende desde el mismo punto de partida, simplemente se añade un elemento más a la suma acumulada. No se reinicia la suma desde cero: se arrastra hacia adelante. Esa observación es la semilla completa de la solución eficiente.
La recurrencia escondida dentro de la fuerza bruta
Una vez que ve que el bucle interno solo hace “seguir sumando a la misma suma acumulada”, puede hacerse una pregunta más precisa: ¿de verdad necesito reiniciar el bucle externo cada vez? Si la suma acumulada se ha vuelto tan negativa que arrastra hacia abajo todo lo que viene después, lo correcto es abandonarla y empezar de cero desde el elemento actual. Si la suma acumulada sigue siendo positiva, arrastrarla ayuda.
Esa decisión —extender o reiniciar— es exactamente la forma de Kadane's algorithm, que formalmente es una recurrencia de programación dinámica: el maximum subarray que termina en el índice i es o bien el elemento en i por sí solo, o bien el elemento en i sumado al maximum subarray que termina en i-1. Usted está reduciendo dos bucles anidados a una sola pasada porque ha identificado que el estado del bucle interno puede arrastrarse en lugar de recalcularse.
Use el guion de Kadane que el entrevistador espera oír
Por qué la regla de reinicio parece rara hasta que la dice en voz alta
La regla de reinicio es la parte que los candidatos suelen explicar peor al hablar de Kadane's algorithm. Dicen algo como “reiniciamos cuando la suma se vuelve negativa”, que se acerca, pero no es del todo correcto, y un entrevistador con experiencia lo va a explorar enseguida. La formulación más precisa es esta: cuando la suma acumulada es negativa, arrastrarla al siguiente elemento hace que la contribución de ese elemento sea peor que si empezáramos de nuevo. Un prefijo negativo siempre perjudica. Empezar de cero desde el elemento actual siempre es al menos tan bueno como arrastrar una suma negativa.
No es un truco ni una heurística. Es una consecuencia de la recurrencia: `current_max = max(nums[i], current_max + nums[i])`. Cuando `current_max` es negativo, `nums[i]` por sí solo es mayor que `current_max + nums[i]`, así que se toma solo `nums[i]`. El reinicio es simplemente la matemática.
Cómo se ve esto en la práctica
Aquí tiene la explicación memorizable: dígala en voz alta antes de la entrevista:
"Voy a mantener dos variables: current_sum, que es la suma máxima de un subarray que termina en el índice actual, y best_sum, que es la mejor suma vista en cualquier parte hasta ahora. En cada índice me pregunto: ¿es mejor extender el subarray actual o empezar de cero desde este elemento? Eso es simplemente tomar el máximo entre el elemento actual solo y el elemento actual más current_sum. Después de actualizar current_sum, actualizo best_sum si current_sum es mayor. Una sola pasada, espacio constante, O(n) de tiempo."
Ese es todo el guion. Es preciso, nombra las variables, explica la decisión y no suena memorizado porque describe una decisión en cada paso en lugar de un procedimiento.
La línea que separa una buena respuesta de una memorizada
La pista que usa un entrevistador para distinguir una respuesta razonada de una memorizada es si el candidato puede explicar qué ocurre en un índice concreto. “En el índice 3, current_sum es negativo, así que se reinicia con nums[3]” es una respuesta razonada. “Reiniciamos cuando la suma se vuelve negativa” es un eslogan. Practique narrando la decisión en cada índice durante su recorrido manual: esa narración es lo que hace que la explicación parezca vivida y no recitada.
La cobertura de GeeksforGeeks sobre el algoritmo de Kadane respalda las afirmaciones de O(n) de tiempo y O(1) de espacio, y merece la pena revisarla para confirmar que la nomenclatura de sus variables coincide con la convención habitual.
Haga el recorrido manual del ejemplo estándar sin perder el hilo
El ejemplo que parece gustarle a todo entrevistador
El array [-2, 1, -3, 4, -1, 2, 1, -5, 4] es el ejemplo canónico por una razón: contiene varios reinicios, una larga racha de extensiones rentables y un elemento positivo engañoso al final que no pertenece al subarray contiguo óptimo. Pone a prueba si usted entiende de verdad la decisión en cada paso o si solo está asociando patrones para “tomar los números grandes”.
La respuesta correcta es 6, procedente del subarray contiguo [4, -1, 2, 1] que empieza en el índice 3.
Cómo se ve esto en la práctica
Recorra el array índice por índice, narrando mientras avanza:
- Índice 0, valor -2: current_sum = max(-2, -2) = -2. best_sum = -2.
- Índice 1, valor 1: current_sum = max(1, -2+1) = max(1, -1) = 1. Reinicio. best_sum = 1.
- Índice 2, valor -3: current_sum = max(-3, 1-3) = max(-3, -2) = -2. best_sum = 1.
- Índice 3, valor 4: current_sum = max(4, -2+4) = max(4, 2) = 4. Reinicio. best_sum = 4.
- Índice 4, valor -1: current_sum = max(-1, 4-1) = max(-1, 3) = 3. Extender. best_sum = 4.
- Índice 5, valor 2: current_sum = max(2, 3+2) = 5. Extender. best_sum = 5.
- Índice 6, valor 1: current_sum = max(1, 5+1) = 6. Extender. best_sum = 6.
- Índice 7, valor -5: current_sum = max(-5, 6-5) = 1. Extender. best_sum = 6.
- Índice 8, valor 4: current_sum = max(4, 1+4) = 5. Extender. best_sum = 6.
Respuesta final: 6. Los momentos clave son los reinicios en los índices 1 y 3, y el hecho de que el 4 final en el índice 8 no supera la mejor suma encontrada antes. Narre esos momentos explícitamente: no se limite a escribir números en una pizarra y esperar que el entrevistador siga el hilo.
Responda a los seguimientos antes de que se conviertan en trampas
El caso de todos los números negativos es donde una inicialización descuidada lo arruina todo
Si inicializa best_sum en cero, devolverá cero para un array como [-3, -1, -2]. Eso es incorrecto: la respuesta correcta es -1, porque el problema pide la suma máxima de un subarray y un subarray de un solo elemento es válido. Cero no es alcanzable a partir de ningún subarray contiguo de esta entrada.
La solución es inicializar best_sum con el primer elemento del array, no con cero. O, equivalentemente, inicializarlo a menos infinito. No es un caso límite menor: es una prueba deliberada de si de verdad entiende las restricciones del problema en lugar de haberse aprendido una solución para ejemplos dominados por números positivos. En una entrevista sobre maximum subarray, este seguimiento aparece con suficiente frecuencia como para que deba tratarlo como parte de la respuesta base y no como una ocurrencia tardía.
Cómo se ve esto en la práctica
Aquí tiene un guion de seguimiento que cubre complejidad, inicialización y el error del reinicio en una sola pasada:
"La complejidad temporal es O(n): una pasada por el array. La complejidad espacial es O(1): solo estamos siguiendo dos variables, independientemente del tamaño de entrada. En el caso de todos los números negativos, la clave es la inicialización: best_sum empieza en nums[0], no en cero, así que siempre devolvemos el elemento menos negativo en lugar de un cero ficticio. La regla de reinicio sigue siendo válida —reiniciamos cuando current_sum arrastraría hacia abajo al siguiente elemento—, pero en un array totalmente negativo, reiniciaremos en casi todos los pasos, y eso es correcto."
Esa respuesta cierra tres líneas de seguimiento a la vez. Los entrevistadores que preguntan por el caso de todos los negativos están comprobando específicamente si usted inicializó correctamente; una respuesta clara aquí indica que ha pensado el problema y no ha copiado una solución.
Devolver los límites es un pequeño cambio, no un problema nuevo
Cuando un entrevistador le pide devolver el subarray real en lugar de solo la suma, muchos candidatos entran en pánico y recurren a un enfoque completamente distinto. No lo haga. Se aplica la misma lógica de O(n): solo debe llevar tres variables adicionales: start (el inicio candidato del subarray actual), end (el final actual) y best_start (el inicio confirmado del mejor subarray visto hasta ahora).
Cuando reinicie current_sum a nums[i], actualice start a i. Cuando actualice best_sum, registre best_start = start y end = i. Al final, devuelva nums[best_start:end+1]. El algoritmo no cambia. El seguimiento de estado añade tres variables y unas pocas líneas de asignación. Explíqueselo al entrevistador exactamente así: “Es el mismo algoritmo con un poco de contabilidad adicional; llevaré el inicio de la ventana actual y actualizaré los límites confirmados cada vez que encuentre una nueva mejor suma”.
CLRS Chapter 4 trata el problema de maximum subarray en detalle y es la referencia autorizada para el análisis de complejidad si quiere citar una fuente durante una entrevista técnica.
Use la respuesta como plantilla para variantes más grandes
Por qué el entrevistador puede pedir una variante en lugar de la respuesta base
Una vez que haya dado una explicación clara de Kadane, algunos entrevistadores pasarán a una variante, no para engañarle, sino para ver si entiende la estructura subyacente o solo la solución superficial. La variante más común es la suma máxima de subarray circular: ¿cuál es la suma máxima de subarray si el array se “envuelve” (es decir, el subarray puede ir del final del array al principio)?
Cómo se ve esto en la práctica
La variante circular tiene una solución elegante que reutiliza Kadane's algorithm dos veces. La suma máxima de subarray en un array circular es o bien:
- La suma máxima estándar de subarray (la respuesta no se envuelve), o
- La suma total del array menos la suma mínima de subarray (la respuesta se envuelve, así que se excluye la sección intermedia mínima)
Primero ejecuta Kadane hacia adelante para obtener el máximo, luego ejecuta una versión de Kadane para el subarray mínimo (invirtiendo las comparaciones) para obtener el mínimo, reste eso del total y tome el mayor de los dos resultados. Un caso límite: si todos los elementos son negativos, la opción 2 daría cero (total menos total), así que en ese caso se devuelve la opción 1.
Lo que conviene decirle al entrevistador es: “La variante circular reutiliza la misma lógica de O(n): no estoy buscando un algoritmo nuevo, sino aplicando la misma estructura de decisión dos veces con objetivos distintos”. Ese enfoque demuestra que usted entiende Kadane's algorithm como un patrón y no como una respuesta memorizada. Para un tratamiento detallado de la variante circular, LeetCode Problem 918 ofrece un enunciado canónico y soluciones de la comunidad que vale la pena revisar.
Cómo Verve AI puede ayudarle a prepararse para su entrevista sobre maximum subarray
El problema estructural que resuelve esta guía —saber el algoritmo pero trabarse al explicarlo bajo presión en vivo— solo se corrige con ensayo y retroalimentación, no con lectura. Un guion que usted haya leído una vez se deshace en cuanto un entrevistador pregunta “¿por qué funciona ese reinicio?”. Necesita decir la explicación en voz alta, escucharse a sí mismo y recibir una respuesta que refleje lo que un entrevistador real cuestionaría de verdad.
Verve AI Interview Copilot está diseñado precisamente para cerrar esa brecha. Escucha en tiempo real su explicación mientras la da —no una respuesta escrita de antemano, sino lo que usted realmente dice— y responde a lo que ha dicho, incluidas las partes que pasó por alto o las transiciones que no funcionaron. Si dijo “reiniciamos cuando la suma es negativa” y omitió la discusión sobre la inicialización, Verve AI Interview Copilot lo detectará igual que lo haría un entrevistador real. El ciclo de práctica es la conversación en vivo, no un cuestionario de opción múltiple.
Verve AI Interview Copilot también realiza entrevistas simuladas sobre toda la secuencia: definición del problema, recorrido por fuerza bruta, derivación de Kadane, recorrido manual y seguimientos. Puede ensayar la apertura de 60 segundos, ser interrumpido a mitad de la explicación y practicar cómo recuperarse, que es la habilidad real que se evalúa en la entrevista. Permanece invisible mientras usted resuelve el problema, de modo que la sesión se siente como una entrevista real y no como una herramienta de práctica con ruedines.
FAQ
P: ¿Cómo explico maximum subarray de forma clara y segura en una entrevista?
Empiece con la definición del problema antes de tocar el código: nombre la entrada, defina qué significa “contiguous”, indique la salida y dé un ejemplo concreto con la respuesta esperada. Esa apertura de 45 segundos le indica al entrevistador que está razonando sobre el problema y no recitando una solución memorizada. Luego diga que empezará con fuerza bruta y avanzará hacia la respuesta eficiente.
P: ¿Cómo derivo el algoritmo de Kadane a partir del enfoque de fuerza bruta?
El bucle interno de la fuerza bruta solo hace esto: “seguir sumando a la misma suma acumulada desde un índice inicial fijo”. Una vez que lo ve, puede preguntarse: ¿de verdad tengo que reiniciar el bucle externo cada vez, o puedo arrastrar la suma acumulada hacia adelante? Si la suma acumulada es positiva, arrastrarla ayuda a los elementos futuros. Si es negativa, empezar de cero desde el elemento actual siempre es mejor. Esa decisión —extender o reiniciar— es toda la recurrencia que hay detrás de Kadane's algorithm.
P: ¿Por qué reiniciamos la suma acumulada cuando empeora respecto a empezar de cero?
Porque un prefijo negativo reduce de forma estricta la contribución de todos los elementos que le siguen. La recurrencia es `current_sum = max(nums[i], current_sum + nums[i])`. Cuando current_sum es negativo, `nums[i]` por sí solo es mayor que `current_sum + nums[i]`, así que la matemática le dice que reinicie. No es una heurística: es la consecuencia directa de la recurrencia.
P: ¿Cómo manejo un array en el que todos los números son negativos?
Inicialice best_sum con el primer elemento del array, no con cero. En un array totalmente negativo, la respuesta correcta es el elemento individual menos negativo; cero no puede obtenerse a partir de ningún subarray contiguo. Si inicializa a cero, devolverá una respuesta incorrecta. Por lo demás, el algoritmo funciona igual; simplemente reiniciará en casi todos los pasos.
P: ¿Cómo puedo hacer un recorrido manual del ejemplo estándar sin perderme?
Lleve dos columnas: current_sum y best_sum. En cada índice, aplique la recurrencia para actualizar current_sum y luego compruebe si supera a best_sum. Narre la decisión en voz alta —“en el índice 3, current_sum se volvió negativo, así que reinicié a 4”— en lugar de limitarse a escribir números. Esa narración es lo que el entrevistador está escuchando realmente.
P: ¿Qué debo decir si el entrevistador me pregunta por la complejidad temporal y espacial y por qué?
O(n) de tiempo porque da exactamente una pasada por el array. O(1) de espacio porque solo está siguiendo dos variables —current_sum y best_sum— sin importar el tamaño de entrada. El “por qué” importa: no está guardando subarrays intermedios ni estructuras auxiliares. El espacio constante es una consecuencia directa de que la recurrencia solo necesita el resultado del paso anterior.
P: ¿Cómo devuelvo los límites del subarray real en lugar de solo la suma?
Lleve tres variables adicionales: un índice de inicio candidato (que se actualiza cada vez que reinicia) y los índices de inicio y fin confirmados (que se actualizan cada vez que encuentra un nuevo best_sum). El algoritmo sigue siendo O(n) con O(1) de espacio: solo añade unas pocas asignaciones por paso. Explíqueselo al entrevistador como contabilidad sobre la misma lógica, no como un algoritmo nuevo.
El guion ya está en su bolsillo
La presión de una entrevista sobre maximum subarray no está en el algoritmo, sino en el momento justo antes de empezar a escribir, cuando tiene que decir algo coherente a una persona que le está observando pensar. Ese momento es el que esta guía ha ido preparando. Ahora tiene una apertura de 60 segundos que define el problema con claridad, una derivación que muestra que entiende por qué funciona Kadane's algorithm y no solo que funciona, un recorrido manual paso a paso que puede seguir sin perder el hilo, y un guion de seguimiento conciso que cubre inicialización, complejidad y seguimiento de índices sin ponerse nervioso.
Ensaye la explicación de 60 segundos una vez antes de su próxima entrevista, no diez. Una pasada deliberada en voz alta, narrando la decisión en cada índice, vale más que diez relecturas silenciosas de esta página.
Verve AI
Contenido