Counterexample to removing a longest increasing subsequence
= Counterexample to removing a longest increasing subsequence
Repeatedly removing a longest <strictly increasing subsequence> need not minimise the number of increasing subsequences in a partition. In $(2,4,1,3)$, removing $(2,3)$ leaves the decreasing pair $(4,1)$, for three subsequences overall. The partition $(2,4)$ and $(1,3)$ uses only two and is optimal because the original sequence is not increasing.