有一个整数数组，我一定要得到k具有长度范围内的序列号（最大 - 子序列的分）小于等于R。有长度为k的序列的数量的长度的K-1的序列和数目的关系的 ？ 我试图解决在SPOJ实践问题。我不想完整的解决方案，只是点我朝着正确的方向/建议/提示。

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.

我在想一个deque的结构来维持分钟和数组的最大元素高达一定index.However，当k接近N，这将成为接近O（N * N），这是太慢了，我理想情况下为O（n）解决方案或O-寻找（N * log n）的解决方案。这将是最好的，如果我可以计算出K = 1到K = N使用递归/迭代关系作为可能再次需要相同的答案所需的值

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

推荐答案

这是一个deque一个完美的应用程序。见我的回答here.

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

您应该能够适应，对于几乎没有改变您的需求，让您的 O（N）解决方案。

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