 Solution

TakeIts 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 three subsequences in total.

However, $(2,4)$ and $(1,3)$ partition the original sequence into 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.