 Solution

Track the first row after any prefix of the input permutation. Its $j$th entry is the smallest possible final value of an increasing subsequence of length $j$ in that prefix. This minimum-tail invariant follows inductively from the row-insertion update.

Indeed, when a new value $z$ replaces the first first-row entry larger than it, at position $r$, the previous entry in position $r-1$ is smaller than $z$ when $r>1$. An increasing subsequence ending there can be extended by $z$, so $z$ supplies a new attainable tail of length $r$. It improves the old length-$r$ minimum. The minima for shorter lengths were already smaller than $z$ and remain unchanged; a longer subsequence ending at $z$ is impossible because its previous tail would have to be smaller than $z$, contradicting the choice of $r$. If no first-row entry exceeds $z$, it appends and creates a new longest subsequence. This proves the invariant at every step.

In particular, the number of first-row cells is the maximum increasing-subsequence length. At the final tableau it is ${\lambda }_1$, soThis proves the required nonextension assertion, even without requiring the first-row tuple itself to occur as a subsequence.

That occurrence is not automatic for a general permutation. For example the word $2,4,3,1$ gives $P$ with rows $(1,3),(2),(4)$. Its first-row tuple $(1,3)$ is not a subsequence of the word, because one occurs after three. The first row collects minimum tails for different subsequence lengths; those tails need not come from one common subsequence. If the source's premise is read as an additional hypothesis that the tuple does occur, the preceding maximum-length proof establishes its claimed maximality directly.

The invariant is the first row of RSK as a minimum-tail table.