Subarray máximo y subarray de producto máximo

El problema Maximum Subarray consiste en encontrar el subarreglo contiguo dentro de un arreglo unidimensional de números que tenga la suma más grande. Por ejemplo, en [-2, 1, -3, 4, -1, 2, 1, -5, 4], el subarreglo [4, -1, 2, 1] produce la suma máxima de 6. Un enfoque de fuerza bruta O(n²) comprueba todos los subarreglos, pero el algoritmo de Kadane lo resuelve en O(n).

El algoritmo de Kadane recorre el arreglo una sola vez y mantiene un current_sum acumulado. En cada elemento, debe decidir: ¿es mejor extender el subarreglo existente o comenzar de nuevo desde este elemento? Si current_sum se vuelve negativo, solo perjudicaría a cualquier subarreglo futuro, por lo que se reinicia. La recurrencia es current_sum = max(num, current_sum + num).

Recorramos el algoritmo de Kadane sobre [-2, 1, -3, 4, -1, 2, 1, -5, 4]: comenzamos con curr=-2, max=-2. En 1: curr=max(1,-2+1)=1, max=1. En -3: curr=max(-3,1-3)=-2, max=1. En 4: curr=max(4,-2+4)=4, max=4. En -1: curr=3, max=4. En 2: curr=5, max=5. En 1: curr=6, max=6. En -5: curr=1. En 4: curr=5, max=6. El algoritmo identifica correctamente el subarreglo que termina en el índice 6 como el óptimo.

Si en la entrevista le piden devolver el subarreglo completo (no solo la suma), debe realizar un seguimiento de los índices inicial y final. Cuando reinicie (porque num > current_sum + num), actualice un temp_start. Cuando actualice max_sum, guarde temp_start como start y el índice actual como end. Esto añade un coste adicional de O(1) al mismo algoritmo de O(n).

El problema Maximum Product Subarray es más complicado que la variante de suma debido a los números negativos. Dos números negativos producen un resultado positivo, por lo que un producto muy negativo puede convertirse en el máximo al multiplicarse por otro negativo. Para [2, 3, -2, 4], la respuesta es 6 ([2, 3]). Para [-2, 0, -1], la respuesta es 0. Debemos realizar un seguimiento de los productos máximo y mínimo en cada paso.

La idea clave es la siguiente: en cada posición, el producto máximo actual es uno de estos valores: num, max_so_far * num o min_so_far * num (este último resulta útil cuando un número negativo convierte el mínimo en máximo). De forma similar, se calcula el mínimo. Actualice ambos valores, cur_max y cur_min, simultáneamente usando los valores anteriores para evitar utilizar valores ya actualizados en el mismo paso.

Considere [-3, -10, 5]. Después de procesar -3: max=-3, min=-3. Después de -10: los candidatos son (-10, 30, 30) → max=30, min=-10. Después de 5: los candidatos son (5, 150, -50) → max=150. Sin realizar un seguimiento de min_prod, no detectaría el cambio que ocurre cuando un mínimo muy negativo se multiplica por otro número negativo. Calcule siempre max y min a partir de los mismos valores anteriores para evitar un error de lectura de valores obsoletos.

Un cero en el arreglo reinicia ambos productos acumulados a cero, lo que divide eficazmente el arreglo en subarreglos independientes. Cuando num = 0, tanto max_prod * 0 = 0 como min_prod * 0 = 0, por lo que los tres candidatos se convierten en 0 y se conserva el máximo del resultado anterior. No se necesita código para casos especiales: la fórmula general gestiona los ceros de forma natural.

Un enfoque alternativo recorre el arreglo de izquierda a derecha y de derecha a izquierda, reiniciando el producto acumulado a 1 cuando encuentra un cero. El subarreglo de producto máximo nunca atraviesa un cero, por lo que, si un número negativo produce un resultado desfavorable en una dirección, el recorrido inverso detectará el cambio. Este enfoque es elegante, pero en las entrevistas suele esperarse más el método de seguimiento de mínimos y máximos.

Los subarreglos de suma y de producto se diferencian en aspectos importantes. En la suma, los negativos siempre son perjudiciales, por lo que debe reiniciar de forma voraz. En el producto, dos negativos pueden ser beneficiosos, así que debe realizar un seguimiento de ambos extremos. Además, los ceros detienen los productos, mientras que solo son ligeramente perjudiciales para las sumas. Al explicarlo en una entrevista, reconozca explícitamente estas diferencias y explique por qué es necesario realizar un seguimiento del mínimo antes de escribir código.

Tanto el algoritmo de Kadane (suma máxima) como el seguimiento de mínimos y máximos (producto máximo) se ejecutan en tiempo O(n) y utilizan espacio O(1). Consejos clave para la entrevista: (1) Para la suma máxima, mencione la alternativa de divide y vencerás O(n log n) para demostrar amplitud de conocimientos. (2) Para el producto máximo, destaque que debe actualizar min_prod y max_prod simultáneamente a partir de los valores anteriores para evitar usar datos obsoletos. (3) Aclare siempre lo siguiente: ¿puede estar vacío el arreglo? ¿Debe el subarreglo ser no vacío? (Sí, por convención debe ser no vacío).

Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

En esta lección aprendió: el algoritmo de Kadane resuelve el subarreglo de suma máxima en O(n) eligiendo extenderlo o reiniciarlo en cada elemento, el subarreglo de producto máximo requiere realizar un seguimiento de los productos acumulados mínimo y máximo debido a los cambios de signo de los números negativos y los ceros reinician de forma natural el producto acumulado sin necesidad de código para casos especiales. A continuación, exploraremos el problema Word Break mediante una tabla de DP unidimensional.