Dada una secuencia de N números, extraiga el número de secuencias de longitud K que tengan un rango menor que R?

Hay una matriz de enteros, tengo que encontrar el número de secuencias de longitud K con rango ( max - min de la subsecuencia) menor que R. Hay una relación entre el número de secuencias de longitud k y el número de secuencias de longitud K-1? Estoy tratando de resolver una pregunta de práctica sobre SPOJ. No quiero la solución completa, solo apúntame en la dirección correcta / sugerencia / sugerencia.

Estaba pensando en una estructura similar a un deque para mantener los elementos mínimo y máximo de la matriz hasta un cierto índice. Sin embargo, cuando k está más cerca de n, esto se acercaría a o (n * n) que es demasiado lento, idealmente soy mirando la solución O (n) o la solución O (n * log n). Sería mejor si puedo calcular el valor requerido para K = 1 a K = N usando una relación de recursión / iteración ya que la misma respuesta podría ser requerida nuevamente

Esta es una aplicación perfecta para un deque. Vea mi respuesta aquí .

Debe poder adaptar eso a sus necesidades casi sin cambios, dándole una solución O(N) .