Longest "bounded" subsequence
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&amp;\text{if }\ell=i\\\pi(\ell)+1/2&amp;\text{if }\ell\ne i,\end{cases}$$

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