= Solution
Read “subsequence” in its usual sense: selected indices increase in the given input order. First sort each box's dimension vector, in $O(nd\log d)$ total time. Let $F[j]$ be the maximum number of boxes in a fitting <subsequence> ending at index $j$. Process $j=1,\ldots,n$ and compute
$$
F[j]=1+\max\bigl(\{F[i]:i<j,\ a_{i,r}<a_{j,r}\text{ for every }1\le r\le d\}\cup\{0\}\bigr).
$$
The last selected box before $j$, if any, supplies exactly one of these candidates; conversely an optimal candidate subsequence can be extended by $j$. <Induction> on $j$ proves the <box nesting> recurrence. Store a maximizing predecessor index and reconstruct from an index maximizing $F[j]$. For $n=0$, return the empty subsequence.
There are $O(n^2)$ candidate pairs, each requiring $O(d)$ coordinate comparisons. Hence \b[$O(nd\log d+n^2d)$ <running time> and $O(nd+n)$ storage] suffice, including sorted vectors, table entries and reconstruction pointers. It is unnecessary to store every fitting pair.
If “subsequence” was intended to allow arbitrary reordering, build the containment <Directed acyclic graph> instead: include every fitting ordered pair, then find its longest chain. Strict increase of the smallest sorted dimension gives a <topological sorting> by that dimension. The same pair-testing bound applies, but the index restriction must then be removed. These two interpretations differ: input boxes $(3,3),(2,2)$ have a longest order-preserving subsequence of one box, but an unrestricted nesting chain of two.
Back to article page
