Primero tenga en cuenta que si se le da un segmento y se le pide que lo haga mejor haciendo un intercambio, no tiene sentido intercambiar elementos dentro del segmento, si vamos a intercambiar siempre debemos intercambiar el elemento más grande que no esté en el segmento con el más pequeño uno en el segmento (si esto hace que la suma sea más grande, por supuesto).
Ahora, ¿cómo encontramos la suma óptima?
si no hicimos ningún intercambio en absoluto, entonces esta es una submatriz de suma máxima normal que se puede resolver fácilmente usando el algoritmo de dividir y conquistar o kadanes.
si podemos hacer un intercambio, seleccionamos un elemento que no está en la submatriz y lo intercambiamos con un elemento en la submatriz, de modo que la submatriz podría estar completamente a su izquierda o completamente a la derecha (q i).
supongamos que está a su izquierda, ahora el problema se vuelve, para cada uno encuentro el subconjunto de suma máxima que termina en algún lugar antes de iy eliminamos un elemento de él.
- ¿Cuáles son las listas vinculadas en Java y qué las hace mejores que las matrices normales?
- ¿Cuál es la intuición detrás del algoritmo de clasificación rápida de múltiples claves?
- ¿Cuál es el algoritmo detrás de la creación de una nueva fuente que solo muestra publicaciones de tus seguidores?
- ¿Cuáles son las ventajas de las pilas en la estructura de datos?
- ¿Cuál es el tema más importante en la estructura de datos y algoritmos en la programación en C?
para resolver tal problema definir
f [i] = submatriz máxima que termina en la posición i-ésima
g [i] = submatriz máxima que termina en la posición i-ésima con un elemento eliminado.
tenemos f [i] = max (f [i-1] + a [i], a [i])
y g [i] = max (f [i-1], a [i] + g [i-1])
ahora el resultado se convierte en max {a [i] + max {g [0],…, g [i-1]}
tenemos que ejecutar el algoritmo en la matriz y es inverso para manejar el otro caso.
