= Solution
Take
$$
\boxed{S=(2,4,1,3).}
$$
Its longest <strictly increasing subsequences> have length two. A subsequence starting with $2$ can continue with $4$ or with $3$, but cannot use both in increasing order; one starting at $1$ has only $3$ after it.
The specified <greedy algorithm> may choose the longest increasing subsequence $(2,3)$. The remaining sequence is $(4,1)$, which needs two singleton increasing subsequences. The algorithm then uses \b[three] subsequences in total.
However, $(2,4)$ and $(1,3)$ partition the original sequence into \b[two] increasing subsequences. One is impossible because the original sequence is not increasing. Hence two is optimal and the greedy choice is suboptimal. This establishes the <counterexample to removing a longest increasing subsequence> without relying on a tie-breaking rule: the problem asks for a longest choice that can fail.
Back to article page
