[Solved]: Longest "bounded" subsequence

Problem Detail: 

Given a sequence of comparable objects $a_1, a_2, \ldots a_n,$ how quickly can we find the longest subsequence $s$ such that $s_i > s_1$ for $i > 1$? Or equivalently, how quickly can we find

$$ \underset{i}{\arg\max} \; \# \{j \mid a_j > a_i, i < j \le n \} $$

Can it be done in less than $\Omega(n\,\lg n)$ comparisons in the worst case?

A $\Theta(n\,\lg n)$ algorithm is to scan from right to left, inserting each element into a balanced tree, keeping track of how many elements in the tree are larger.

This was inspired by this thread on reddit.

Asked By : Tavian Barnes

Answered By : David Eisenstat

No, $\Omega(n\log n)$ comparisons are required. Let $k = \Theta(n)$ be an integer parameter and consider the following family of inputs.

$$k+1,\:k+2,\:k,\:k+2,\:k-1,\:k+2,\:\ldots,\:2,\:k+2,\:1,\:k+2,\:x_1,\:x_2,\:\ldots,\:x_k$$

Note that, for $a\in\{1,\:2,\:\ldots,\:k+1\}$, the maximum bounded subsequence beginning with $a$ consists of $a$, then $a$ copies of $k+2$, then a subsequence of $x_1,x_2,\ldots,x_k$. It is not profitable to begin anywhere else, since the maximum bounded subsequence beginning with $k+1$ has length at least $k+2$.

Let the adversary in this lower bound choose a random permutation $\pi$ on $\{1,2,\ldots,k\}$ and answer as though $x_j=\pi(j)+1/2$. This setting ensures that every maximum bounded subsequence beginning with $a\in\{1,\:2,\:\ldots,\:k-1\}$ has length exactly $k+2$. By the following argument, however, the algorithm cannot be sure of this fact unless it sorts $x_1,x_2,\ldots,x_k$.

Suppose that the algorithm cannot infer the order of $x_i$ and $x_j$. Without loss of generality, assume that $i=\pi^{-1}(\pi(j)-1)$, so that $x_i$ immediately precedes $x_j$ in the imagined sorted order of $x_1,x_2,\ldots,x_k$. It is consistent with the algorithm's observations that

$$x_\ell=\begin{cases}\pi(j)+1/2&\text{if }\ell=i\\\pi(\ell)+1/2&\text{if }\ell\ne i,\end{cases}$$

which would give rise to a bounded subsequence of length $k+3>k+2$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30576

3.2K people like this

 Download Related Notes/Documents