Tengo una matriz de enteros positivos. Por ejemplo:

 [1, 7, 8, 4, 2, 1, 4]

Una "operación de reducción" encuentra el prefijo de matriz con el promedio más alto y lo elimina. Aquí, un prefijo de arreglo significa un subarreglo contiguo cuyo extremo izquierdo es el comienzo del arreglo, como [1] o [1, 7] o [1, 7, 8] arriba. Los empates se rompen tomando el prefijo más largo.

 Original array: [ 1, 7, 8, 4, 2, 1, 4] Prefix averages: [1.0, 4.0, 5.3, 5.0, 4.4, 3.8, 3.9] -> Delete [1, 7, 8], with maximum average 5.3 -> New array -> [4, 2, 1, 4]

Repetiré la operación de reducción hasta que la matriz esté vacía:

 [1, 7, 8, 4, 2, 1, 4] ^ ^ [4, 2, 1, 4] ^ ^ [2, 1, 4] ^ ^ []

Ahora, en realidad no es necesario realizar estas modificaciones de matriz; Solo estoy buscando la lista de longitudes de prefijos que se eliminarían con este proceso, por ejemplo, [3, 1, 3] arriba.

¿Cuál es un algoritmo eficiente para calcular estas longitudes de prefijo?

El enfoque ingenuo es volver a calcular todas las sumas y promedios desde cero en cada iteración para un algoritmo O(n^2) . He adjuntado el código de Python para esto a continuación. Estoy buscando alguna mejora en este enfoque, preferiblemente, cualquier solución por debajo O(n^2) , pero también sería útil un algoritmo con la misma complejidad pero mejores factores constantes.

Estas son algunas de las cosas que he intentado (sin éxito):

1. Mantenimiento dinámico de sumas de prefijos, por ejemplo, con un árbol indexado binario . Si bien puedo actualizar fácilmente las sumas de prefijos o encontrar una suma máxima de prefijos en O(log n) , no he encontrado ninguna estructura de datos que pueda actualizar el promedio , ya que el denominador en el promedio está cambiando.
2. Reutilizando las 'clasificaciones' anteriores de promedios de prefijos: estas clasificaciones pueden cambiar, por ejemplo, en alguna matriz, el prefijo que termina en el índice 5 puede tener un promedio mayor que el prefijo que termina en el índice 6 , pero después de eliminar los primeros 3 elementos, ahora el el prefijo que termina en el índice 2 puede tener un promedio más pequeño que el que termina en 3 .
3. Buscando patrones en donde terminan los prefijos; por ejemplo, el elemento más a la derecha de cualquier prefijo promedio máximo es siempre un máximo local en la matriz, pero no está claro cuánto ayuda esto.

Esta es una implementación funcional de Python del método cuadrático ingenuo:

 from fractions import Fraction def find_array_reductions(nums: List[int]) -> List[int]: """Return list of lengths of max average prefix reductions.""" def max_prefix_avg(arr: List[int]) -> Tuple[float, int]: """Return value and length of max average prefix in arr.""" if len(arr) == 0: return (-math.inf, 0) best_length = 1 best_average = Fraction(0, 1) running_sum = 0 for i, x in enumerate(arr, 1): running_sum += x new_average = Fraction(running_sum, i) if new_average >= best_average: best_average = new_average best_length = i return (float(best_average), best_length) removed_lengths = [] total_removed = 0 while total_removed < len(nums): _, new_removal = max_prefix_avg(nums[total_removed:]) removed_lengths.append(new_removal) total_removed += new_removal return removed_lengths

Editar: el código publicado originalmente tenía un error raro con grandes entradas al usar math.isclose() de Python con parámetros predeterminados para la comparación de coma flotante, en lugar de la comparación de fracciones adecuada. Esto se ha corregido en el código actual. Puede encontrar un ejemplo del error en este enlace Pruébelo en línea , junto con un prólogo que explica exactamente qué causa este error, si tiene curiosidad.