Given a sequence of N numbers ,extract number of s

问题:

There is an array of integers ,I have to find the number of sequences of K length having range (max - min of the subsequence) less than equal to R .Is there a relation between Number of sequences of length k and number of sequences of length K-1 ? I am trying to solve a practice question on SPOJ. I don't want the full solution,just point me in the right direction /suggestion/hint.

I was thinking of a deque like structure to maintain min and max elements of the array upto a certain index.However,when k is closer to n ,this would become close to o(n*n) which is too slow ,I am ideally looking at O(n) solution or O(n * log n) solution. It would be best if I can calculate the required value for K=1 to K=N using a recursion/iteration relation as the same answer maybe required again

回答1:

This is a perfect application for a deque. See my answer here.

You should be able to adapt that for your needs with almost no changes, giving you an O(N) solution.