El mejor método que se me ocurre es O (n logn). Se puede hacer usando un enfoque ascendente.
Comience desde el final de la matriz. La respuesta para la posición i-ésima se almacenará en dp [i]. Para calcular dp [i], puede usar el árbol de segmentos para encontrar valores mínimos de i + 1th a i + kth dp. Después de calcular dp [i], este valor se puede insertar en el árbol de segmentación para calcular los valores de furthur dp.
EDITAR: Supongo que uno puede usar deque para obtener el rendimiento O (n). Deque solo almacenará elementos en la ventana actual de modo que estén en orden descendente de atrás hacia adelante. En cada índice i, elimine el elemento en la parte superior de deque si ya no está en el rango i + 1 a i + k. Ahora calcule dp [i]. Empuje este resultado en la parte posterior de deque. Ahora elimine elementos de la deque que están presentes previamente en deque y si son más pequeños que los calculados actualmente dp [i]. Cada elemento se agregará y eliminará una vez, por lo tanto, la complejidad será O (n).
- ¿Cuál es una manera simple de implementar la paginación en una matriz en Javascript?
- ¿Puedo volverme competente en estructuras de datos y algoritmos sin leer el libro CLRS?
- ¿Qué es un programa simple de C ++ para insertar un nodo en una lista vinculada?
- Cómo demostrar que en cada árbol de búsqueda binaria n-nodo hay exactamente n-1 rotaciones posibles
- ¿Cuáles son los mejores algoritmos de clasificación para DBMS?
Este método de eliminación se explica aquí: Máximo de todas las submatrices de tamaño k (Se agregó un método O (n)) – GeeksforGeeks
