Given an array of $n$ pairwise-different positive integers, the problem is to find the longest subsequence that is stack-sortable, i.e. avoiding the permutation pattern $231$.
How fast can this problem be solved? Can it be solved in polynomial time and linear space?