CTCI 9.10

You have a stack of n boxes, with widths wi, height hi, and depths di. The boxes cannot be rotated and can only be stacked on top of one another if each box in the stack is strictly larger than the box above it in width, height and depth. Implemnt a method to build the tallest stack possible, where the height of a stack is the sum of the heights of each box.

CTCI 9.10.java

public ArrayList<Box> findHighest(Box bottom, Box[] boxes, HashMap<Box, ArrayList<Box>> map){
    if(map.contansKey(bottom)) return map.get(bottom);
    int highest = -1;
    ArrayList<Box> highestList= null;
    for(int i = 0; i < boxes.length; i++){
        if(canbeAbove(boxes[i], bottom)){
            ArrayList<Box> thisList = findHighest(boxes[i], boxes, map);
            int thisHighest = hight(thisList);
            if(thisHighest > highest){
                highest = thisHighest;
                highestList = newList;
            }
        }
    }
    if(highestList == null) highestList = new ArrayList<Box>();
    else{
        ArrayList<Box> newList = new ArrayList<>();
        newList.addAll(highestList);
        newList.add(bottom);
    }
    map.put(bottom, highestList);
    return highestList;
}