Divida la entrada por la mitad y considere que la submatriz de suma máxima puede provenir de tres lugares:
- Está completamente en la mitad izquierda.
- Está completamente en la mitad derecha.
- Consiste en una cierta cantidad de elementos más a la derecha de la mitad izquierda y una cierta cantidad de elementos más a la izquierda de la mitad derecha.
Supongamos que resuelve el problema recursivamente en las mitades izquierda y derecha. Entonces conocerá las mejores submatrices que puede obtener que están completamente en cada una de las mitades, para los puntos 1 y 2 anteriores.
Para 3, notamos que el número de elementos a tomar de la mitad izquierda y la mitad derecha debe elegirse independientemente (es decir, ambos deben elegirse para maximizar su contribución a la suma). Entonces, simplemente estamos buscando la suma de prefijos más grande en la submatriz derecha, y la suma de sufijos más grande en la submatriz izquierda, que pueden resolverse trivialmente en O (n) tiempo y O (1) espacio.
- ¿Qué libro debo elegir para aprender algoritmos y estructuras de datos? Ver la descripción.
- Programación de computadoras: Como ingeniero de software, ¿qué cosas crees que son "innecesariamente complicadas"?
- ¿Cuál es la necesidad de determinar la complejidad temporal de un algoritmo o código?
- ¿Cómo funciona un algoritmo de bogosort cuántico?
- Cómo obtener una comprensión profunda y exhaustiva de la optimización de algoritmos en C ++
Entonces es fácil comparar las opciones 1, 2 y 3, y encontrar el máximo.
La recurrencia para la complejidad del tiempo es T (n) = 2T (n / 2) + O (n), lo que nos da T (n) = O (n log n).
Podemos hacer una optimización para resolver este problema en O (n). Si regresamos, para cada caso recursivo, no solo la ubicación del subarreglo óptimo y su suma, sino también la suma total de la matriz y los prefijos y sufijos más grandes, cada caso recursivo solo necesita hacer el trabajo O (1):
full.maxPrefix = max (left.maxPrefix, left.sum + right.maxPrefix)
full.maxSuffix = max(right.maxSuffix, right.sum + left.maxSuffix)
full.sum = left.sum + right.sum
full.maxInner = max(left.maxInner, right.maxInner, left.maxSuffix + right.maxPrefix)
Debería almacenar un poco más de información de contabilidad si desea encontrar la posición de la submatriz máxima también.
Con todos los cálculos para un solo caso que se ejecuta en O (1), la recurrencia ahora es T (n) = 2T (n / 2) + O (1), lo que produce O (n).
Esto parece un método complicado en comparación con la solución estándar O (n) para este problema. Sin embargo, este tipo de enfoque es lo que se necesita, en combinación con un árbol de segmentos, para resolver la versión dinámica de este problema.
La versión dinámica tendría el siguiente enunciado del problema: cree una estructura de datos que, después de un preprocesamiento inicial, pueda admitir set(index, value) y getCurrentMaxSubarraySum() en tiempo O (log n) para ambos. En otras palabras, los elementos arbitrarios de la matriz pueden cambiar y la suma máxima de subarreglos necesita ser recalculada eficientemente entre los cambios.
