Encontrar la suma máxima de subarreglos discontinuos

Este es un problema típico de programación dinámica. El libro proporciona una solución óptima con una complejidad temporal de O (N) y una complejidad espacial de O (1) mediante un análisis paso a paso. Encontré una variante interesante de esta pregunta durante la entrevista, es decir, dada una matriz, escriba un método para encontrar el valor máximo de la suma de subarreglos discontinuos, es decir, dos subarreglos adyacentes cualesquiera en el subarreglo Los elementos deben ser no. -adyacente en la matriz original. También tomando la matriz {1, -2, 3, 5, -1, 2} como ejemplo, la submatriz discontinua con la suma más grande es {1, 5, 2} y el valor de retorno de la función es 8.

Obviamente, la forma más directa de pensar es utilizar el método exhaustivo. Para este tipo de problema de encontrar subarreglos que cumplan las condiciones, no es más que hacer un juicio transversal sobre si cada elemento en el. La matriz original pertenece a la submatriz. Dado que cada elemento tiene la posibilidad de pertenecer o no al subarreglo, la complejidad temporal exhaustiva es O (2 ^ N). Incluso considerando la restricción de "discontinuidad", es decir, después de seleccionar un elemento para que pertenezca a un subarreglo, sus elementos adyacentes no deben seleccionarse y no tendrá mucho impacto en el orden de magnitud de la complejidad temporal. Entonces, obviamente, esta es definitivamente una respuesta estúpida...

Inspirándonos en la pregunta "La belleza de la programación", ¿podemos también usar programación dinámica para resolver esta pregunta? Supongamos que la suma de los subarreglos discontinuos más grandes a partir de la i-ésima posición de la matriz original a es m [i], entonces hay dos posibilidades para su valor: una es el elemento actual a [i] y la siguiente. solución de subproblema de bits m[ i 2 ] (determinada por la propiedad de discontinuidad), la otra no contiene el elemento actual pero es directamente igual a la solución de subproblema superior de un bit anterior m[ i 1 ], entonces podemos escribir la fórmula de recursión como: m[ i ] = max(a[ i ] m[ i 2 ], m[ i 1 ]).

Espera, tal vez quieras decir que parece haber una laguna en esta fórmula recursiva, porque la solución m[i 1] en el dígito anterior puede incluir o no a[i 1] , si m[i 1] no contiene a[i 1], entonces ¿no deberíamos considerar también la posibilidad de a[i] m[i 1]?

¿Es esta fórmula recursiva realmente incapaz de resistir el escrutinio? También podríamos reorganizar nuestro pensamiento: dado que cada elemento en la matriz original tiene dos posibilidades de tomar o no tomar, entonces también corresponde a la suma máxima de las dos submatrices que contienen y no contienen el elemento. Para el elemento en la posición i en la matriz original a, suponga que la suma máxima del subarreglo que contiene el elemento a[i] es s[i], y la suma máxima del subarreglo que no contiene el elemento a[i] es ns [i], por lo tanto, la suma máxima requerida de subarreglos discontinuos m[i] = max(s[i], ns[i]).

Luego, de acuerdo con el significado de la pregunta, podemos ordenar la relación de recursividad de la siguiente manera:

s[ i ] = max(a[ i ] ns[ i 1 ], a[ i ] m[ i 2 ])

ns[ i ] = m[ i 1 ]

m[ i ] = max(a[ i ] ns[ i 1 ], a[ i ] m[ i 2 ], m[ i 1 ])

Lo interesante radica en el término ns[ i ] = m[ i 1 ]. Según él, podemos obtener ns[ i 1 ] = m( i 2), es decir Si m[i 1] no contiene a[i 1], entonces debe ser igual a m[i 2], por lo que a[i] ns[i 1] es equivalente a a[ i] m[i 2], recursividad ¡La fórmula m[ i ] = max(a[ i ] m[ i 2 ], m[ i 1 ]) es correcta!

Inspirándonos en la solución dada en "La belleza de la programación", solo necesitamos usar dos variables para registrar los valores de m[i 2] y m[i 1], y también solo need Este problema se puede resolver con complejidad O(N). El código es el siguiente:

int maxsum(int* a, int n)

{