Longest stack-sortable subsequence

Question

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?

Answer 1

There's a polynomial-time dynamic programming algorithm in section 3.2 of https://ajc.maths.uq.edu.au/pdf/28/ajc_v28_p225.pdf (Albert et al, "Longest subsequences in permutations", Australas. J. Combin. 28 (2003), 225–238)