Box nesting

Represent a $d$-dimensional box by its side-length vector and allow axis permutations. A box fits another when its permuted dimensions are all strictly smaller. Sorting each vector reduces containment to coordinatewise strict comparison, by the sorted-coordinate criterion for box containment. For an input-order-preserving subsequence, the longest chain ending at position $j$ has one plus the greatest chain length at an earlier fitting position. This last-box decomposition proves the dynamic programming recurrence. Sorting all dimensions and testing all ordered index pairs takes $O(nd\log d+n^{2}d)$ running time. Arbitrary reordering is a different convention, handled by the containment Directed acyclic graph.

Let $a_1\le \cdots \le a_d$ and $b_1\le \cdots \le b_d$ be the separately sorted dimension vectors. Matching corresponding ranks proves the forward construction when every $a_i<b_i$. Conversely, if $a_k\ge b_k$, then the $d-k+1$ source dimensions from rank $k$ onward require distinct targets strictly larger than $a_k$, but only the last $d-k$ target ranks could qualify. The pigeonhole principle rules out such a permutation. Strict inequality matters: equal side lengths do not fit under this convention. Sorting and checking gives an $O(d\log d)$ decision algorithm.