Can we get any subsequence of size $\ge \lfloor \frac{n}{2} \rfloor$ in a sorted order from a sequence in linear time?
It's impossible (assuming you only use comparisons). First, we augment all elements with indices: $a[i] \to (a[i], i)$. We'll need this when we'll remove the sequence from the array in linear time.
Consider the following sorting algorithm:
def sort(a):
    subseq = get_sorted_subseq(a)  # Your function. Assume takes O(n) time
    b = a.exclude(subseq)          # Since we know indices, takes O(n) time
    return merge(subseq, sort(b)). # Takes O(n) time (see merge sort) + recursive call of size &lt;= n/2

In result, the running time is $O(n + \frac n2 + \frac n4 + ...) = O(n)$, which violates a well-known lower bound for sorting.