Given input sequence $x_1,...,x_n$, find the longest contigous subsequence $x_i,... x_l$ where each pair $(x_j,x_k)$ satisfies that $|x_j - x_k| \le p$.
I have come up with simple $\mathcal{O}(n^2)$ solution.
I'm sure there is a better way so I'm looking for $\mathcal{O}(n)$ or at least $\mathcal{O(n \log n)}$ solution. Thanks for any help!
You can solve this in $O(n\log n)$ using a Range Minimum Query data structure. This is a data structure that given two indices $i \leq j$ return $\min(x_i,\ldots,x_j)$. We can construct a data structure that answers such queries in $O(1)$ time using $O(n\log n)$ preprocessing. The idea is to compute $\min(x_i,\ldots,x_j)$ for every pair $i \leq j$ such that $j-i+1$ is a power of 2. This can be accomplished in time $O(n\log n)$ using the identity $$\min(x_i,\ldots,x_{i+2^{\ell+1}-1}) = \min\bigl(\min(x_i,\ldots,x_{i+2^\ell-1}),\min(x_{i+2^\ell},\ldots,x_{i+2^\ell+2^{\ell}-1})\bigr). $$ Using this information, we can compute each range minimum query as follows. Given $i\leq j$, let $2^\ell$ be the largest power of 2 such that $2^\ell \leq j-i+1$; we assume that we can compute $\ell = \lceil \log_2 (j-i+1) \rceil$ in constant time. Then $$ \min(x_i,\ldots,x_j) = \min\bigl(\min(x_i,\ldots,x_{i+2^\ell-1}), \min(x_{j-2^\ell+1},\ldots,x_j)\bigr). $$
For each $i$, we use binary search to compute in time $O(\log n)$ the maximal $\ell \leq i$ such that $\min(x_\ell,\ldots,x_i) \geq x_i-p$ and the minimal $r \geq i$ such that $\min(x_i,\ldots,x_r) \geq x_i-p$. Thus $x_\ell,\ldots,x_r$ is the largest interval satisfying your constraint in which $x_i$ is the maximal point. Taking the maximum of $r-\ell+1$ over all $i$ reveals the solution to your task.
