= 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^2d)$ <running time>. Arbitrary reordering is a different convention, handled by the containment <Directed acyclic graph>.
Back to article page
