PROBLEM LINK:
Author: Shivani Srivastava
Tester: Shivani Srivastava
Editorialist: Kaushambi Gujral
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming, Stacks
PROBLEM:
You are given a set of n types of rectangular 3D boxes, where the ith box has height h(i), width w(i) and depth d(i).
You want to create a stack of boxes which is as tall as possible(Jumbo Mystery Box), but you can only stack a box on top of another box
if the dimensions of the 2D base of the lower box are each strictly larger than those of the 2D base of the higher box.
QUICK EXPLANATION:
The problem is similar to the Longest Increasing Subsequence. There are only 3 possibilities to place any box. We can
arrange this in the desired fashion and choose the boxes with the decreasing area.
EXPLANATION:
So we have n boxes. The first thing we will concentrate upon is the box rotations. Remember that each rotation will create more
possibilities for making the stack, and that we have unlimited number of boxes.
We are saying that we can rotate a box and it seems a little complicated, but if you look closely, then we have only 3 unique possibilities
which will have different base areas.
That can be obtained when you place the box in the following manners:

{ h, w, d }

{ w, h, d }

{ d, h, w }
For each given box, we will generate all the possibilities. Since we have unlimited boxes, we will use all the boxes to make the stack
of the maximum height.(Now this problem has been reduced to a variation of Longest Increasing Subsequence.)
To create the stack of maximum height, we need to place the box with max base area at the bottom, on top of that the box with 2nd max base
area and so on.
AUTHORâ€™S AND TESTERâ€™S SOLUTION:
The solution can be found here.