Quizás este proceso sea un poco más lento en caso de un gran número de consultas. Este algoritmo es , es decir, toma O (sqrt (n)) para el preprocesamiento y O (sqrt (n)) para la consulta.
- Divida toda la matriz en partes sqrt (n) de longitud sqrt (n) (casi todas).
- Precalcule para cada parte de la longitud de sqrt (n) lo siguiente:
- Suma total
- suma máxima de subarreglos contiguos
- suma de prefijo máximo (izquierda mejor suma)
- suma máxima de sufijo (mejor suma correcta)
- Cada consulta requerirá no más de 3 * sqrt (n) de tiempo. Para cada consulta (x, y), divida el intervalo (x, a) + (a, b) + (b, y) de modo que el intervalo (a, b) resida completamente sus puntos de intersección. Encuentre la mejor suma sobre (a, b) mi fusión de todos los nodos internos. Para fusionar a nodos:
- total_sum = total_sum_of_first + total_sum_of_second
- max_prefix_sum = max (max_prefix_sum_of_first, total_sum_of_first + max_pref_sum_of_second)
- max_suffix_sum = max (max_suffix_sum_of_second, total_sum_of_second + max_suffix_sum_of_first)
- max_sub_array_sum = max (total_sum, max_prefix_sum, max_suffix_sum, max_sub_array_sum_of_first, max_sub_array_sum_of_second, prefix_sum_of_second + suffix_sum_of_first)
- Encuentre la mejor suma sobre (x, a) si x! = A, utilizando su matriz original en tiempo sqrt (n). Encuentre la mejor suma sobre (b, y) si b! = Y, utilizando su matriz original en tiempo sqrt (n). Ahora tiene tres nodos, combine los tres con el método anterior y finalmente devuelva la respuesta a (x, y).
