Show problems as
Classic problem #1691HardArrayDynamic ProgrammingSorting

Maximum Height by Stacking Cuboids

Real-world version: Tallest Crate Tower
Tracked in this browser only
Read Maximum Height by Stacking Cuboids on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A warehouse holds n rectangular crates. crates[i] lists the three side lengths of crate i in no particular order.

A crate may be set down on any of its faces, so for each crate you are free to decide which of its three sides becomes its width, which becomes its depth and which becomes its height. Rotation is unrestricted, and each crate is oriented independently.

Once oriented, crate i may be placed directly on crate j only if all three of its measurements are no larger than crate j's: width_i <= width_j, depth_i <= depth_j and height_i <= height_j. Equal measurements are allowed.

Pick any subset of the crates and any order for them, orient each one as you like, and build a single tower where every crate rests on the one below it. Return the greatest possible total height. A tower may consist of one crate.

Examples

Example 1

Input
crates = [[1, 1, 10], [2, 2, 20], [3, 3, 30]]
Output
60

Put the crate measuring 3 by 3 by 30 on the floor, the 2 by 2 by 20 crate on top of it and the 1 by 1 by 10 crate on top of that. Each crate's three measurements are no larger than those of the crate below, and the heights add to 60.

Example 2

Input
crates = [[2, 2, 2], [3, 3, 3], [100, 1, 1]]
Output
100

Set the crate with sides 100, 1 and 1 down on its 1 by 1 face so that it stands 100 tall. That single crate is a tower of height 100.

Example 3

Input
crates = [[41, 28, 52]]
Output
52

There is one crate. Resting it on the face measuring 41 by 28 leaves 52 standing vertically, so the tower is 52 high.

Constraints

  • 1 <= crates.length <= 100
  • crates[i].length == 3
  • 1 <= crates[i][j] <= 100

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def tallest_stack(crates: list[list[int]]) -> int:
Java
public int tallestStack(int[][] crates)

More on the same topics