给定N个数字的序列，提取具有范围小于的R长度K序列数？ [英] Given a sequence of N numbers ,extract number of sequences of length K having range less than R?

问题描述

有一个整数数组，我一定要得到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一个完美的应用程序。见我的回答<一href="http://stackoverflow.com/questions/12598260/finding-consecutively-increasing-subsequence-stored-in-a-haphazard-manner/12598726#12598726">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.

这篇关于给定N个数字的序列，提取具有范围小于的R长度K序列数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！