MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

It seems that $O(n \log (n))$ is possible. Just process the array from left to right as follows. At time $t$ we store both $\mathbf{X}_t$ and $\mathbf{Y}_t$ which are respectively the best valid sequence with indices in $[t]$ \{1, \dots, t\}$ and the best valid sequence which ends with$A[t]$. At time$t+1$we update$\mathbf{X}_t$and$\mathbf{Y}_t$as follows. If$(\mathbf{Y}_t, A[t+1])$is a valid sequence of length longer than$\mathbf{X}_t$, then we set $\mathbf{X}_{t+1}:=(\mathbf{Y}_t, A[t+1])$ and $\mathbf{Y}_{t+1}:=(\mathbf{Y}_t, A[t+1])$. Otherwise, we set $\mathbf{X}_{t+1}:=\mathbf{X}_t$ and we can compute$\mathbf{Y}_{t+1}$in$O(\log (n))$-time via binary search. 1 It seems that$O(n \log (n))$is possible. Just process the array from left to right as follows. At time$t$we store both$\mathbf{X}_t$and$\mathbf{Y}_t$which are respectively the best valid sequence with indices in$[t]$and the best valid sequence which ends with$A[t]$. At time$t+1$we update$\mathbf{X}_t$and$\mathbf{Y}_t$as follows. If$(\mathbf{Y}_t, A[t+1])$is a valid sequence of length longer than$\mathbf{X}_t$, then we set $\mathbf{X}_{t+1}:=(\mathbf{Y}_t, A[t+1])$ and $\mathbf{Y}_{t+1}:=(\mathbf{Y}_t, A[t+1])$. Otherwise, we set $\mathbf{X}_{t+1}:=\mathbf{X}_t$ and we can compute$\mathbf{Y}_{t+1}$in$O(\log (n))\$-time via binary search.