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

CC BY-SA 4.0
2019-04-24T01:54:25.010Z
2019-04-24T01:54:25.010Z
David Eppstein
<p>Given an array of <span class="math-container">$n$</span> pairwise-different positive integers, the problem is to find the longest subsequence that is <a href="https://en.wikipedia.org/wiki/Stack-sortable_permutation" rel="nofollow noreferrer">stack-sortable</a>, i.e. avoiding the permutation pattern <span class="math-container">$231$</span>.</p>

<p>How fast can this problem be solved? Can it be solved in polynomial time and linear space?</p>

<ds.algorithms><dynamic-programming>
Longest stack-sortable subsequence
LeechLattice
# Longest stack-sortable subsequence

(Asked by: username_0 on 2019-04-23)

Given an array of $n$ pairwise-different positive integers, the problem is to find the longest subsequence that is [stack-sortable](https://en.wikipedia.org/wiki/Stack-sortable_permutation), i.e. avoiding the permutation pattern $231$.

How fast can this problem be solved? Can it be solved in polynomial time and linear space?

**Tags:** ds.algorithms, dynamic-programming


---

## 1 answers

### Answer by username_1 on 2019-04-24. Score: 4 | Accepted answer

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)


---

