10.29

Idea
Treat every box as a node whose “weight” is its own height. A legal stack is a chain of boxes whose width, height and depth are all strictly decreasing from bottom to top. After ordering the boxes by decreasing size we can compute, for every box, the tallest stack that ends with that box on top – exactly the 3-D analogue of the Longest Increasing Subsequence, except the score we maximise is “total height”, not “length”.

Algorithm
1. sort(boxes, key = (-w, -h, -d)) # largest box comes first
2. let DP[i] = height of tallest stack whose top box is i
let prev[i] = index of the box that lies directly under i in that tallest stack
3. for i = 0 … n-1:
    DP[i] = boxes[i].h # stack with only this box
    prev[i] = NIL
    for j = 0 … i-1: # examine earlier (bigger) boxes
        if boxes[j].w > boxes[i].w and
           boxes[j].h > boxes[i].h and
           boxes[j].d > boxes[i].d and
           DP[j] + boxes[i].h > DP[i]:
             DP[i] = DP[j] + boxes[i].h
             prev[i] = j
4. best = argmax(DP) # index of the tallest overall stack
5. reconstruct the stack by following prev[] from best upwards.

Complexities
• Sorting: O(n log n) • Double loop: O(n²) Overall: O(n²) time, O(n) additional space.

Result
The reconstructed sequence gives the boxes in bottom-to-top order, and the corresponding maximum total height is max(DP). This is the tallest possible stack because for every box we have explored all larger predecessors, ensuring optimal substructure and yielding an optimal solution through dynamic programming.

Back to Chapter 10