Los dos problemas tienen soluciones muy similares. GSS1 es solo GSS3 sin la operación de “actualización”, así que solo explicaré cómo resolver GSS3.
Como sabes, necesitas usar un árbol de segmentos. La única pregunta es qué datos almacenar en cada nodo. Como sabe, el requisito debería ser que sea fácil calcular los datos asociados con un intervalo dado si ya conoce los datos asociados con dos subintervalos cuya unión disjunta es el intervalo dado. Afirmo que los datos que necesita son:
- la suma máxima de subarrays no vacía,
- la suma máxima de prefijo no vacío,
- la suma máxima de sufijo no vacío,
- la suma total
Para calcular la suma máxima de subarreglos no vacíos para un intervalo I que es la unión disjunta de un subintervalo izquierdo L y un subintervalo derecho R, considere tres casos:
- En la programación en C, dada una matriz de tamaño n, ¿cómo encuentras la suma de todas las combinaciones posibles de sus números?
- ¿Cuál es el mejor instituto para estructuras de datos y algoritmos en Hyderabad?
- ¿Qué significa la recursividad en matemáticas?
- ¿Por qué los estudiantes chinos tienen un talento extraordinario en programación y algoritmos?
- ¿Cuál es la mejor estructura de datos para almacenar y realizar una adición de dos números grandes de 512 bits?
- El subconjunto no vacío de suma máxima está contenido dentro de L. En ese caso, es el subconjunto no vacío de suma máxima de L, que ya conocemos.
- El subconjunto no vacío de suma máxima está contenido dentro de R. En ese caso, es el subconjunto no vacío de suma máxima de R, que ya conocemos.
- El subconjunto no vacío de suma máxima está en parte en L y en parte en R. En ese caso, debe ser la combinación del sufijo no vacío de suma máxima de L y el prefijo no vacío de suma máxima de R, que conocemos.
Para obtener la suma máxima de subarreglos no vacíos para un intervalo dado, solo tome el máximo de estos tres casos. No creo que haya mucho que demostrar aquí: no es más que el análisis de casos. Le dejo al lector cómo averiguar cómo calcular la suma máxima de prefijo no vacío y la suma máxima de sufijo no vacío para un intervalo desde los subintervalos. La suma total es, por supuesto, estándar.
Las actualizaciones son fáciles: simplemente establece los cuatro valores para un intervalo de un solo elemento al valor del elemento en sí.
Puede ver el código aquí: t3nsor / SPOJ
