cc150_9_10.java

import java.util.HashMap;
import java.util.LinkedList;

public class Q9_10 {
	
	public static void main(String[] args){
		
		Box[] boxes = new Box[]{new Box(3,4,1),new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2),new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3), new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2), new Box(7, 8, 3),new Box(3, 4, 1), new Box(8, 6, 2)};
		LinkedList<Box> stack = Q9_10.maxHeight(boxes);
		for (Box box : stack) {
            System.out.println(box.toString());
        }
		
	}

	private static LinkedList<Box> maxHeight(Box[] boxes) {
		// TODO Auto-generated method stub
		if(boxes == null || boxes.length == 0)
			return null;
		
		HashMap<Box,LinkedList<Box>> map = new HashMap<Box,LinkedList<Box>>();
		return recMaxheight(boxes,null,map);
		
	}

	private static LinkedList<Box> recMaxheight(Box[] boxes, Box bottom,
			HashMap<Box, LinkedList<Box>> map) {
		// Bottom is already in the list, return the list
		if(map.containsKey(bottom)){
			return new LinkedList<Box>(map.get(bottom));
		}
		
		LinkedList<Box> maxstack = new LinkedList<Box>();
		for(int i = 0; i < boxes.length; i ++){
			if(bottom == null || (boxes[i].width < bottom.width && boxes[i].height < bottom.height && boxes[i].depth < bottom.depth)){
				LinkedList<Box> stack = recMaxheight(boxes, boxes[i],map);
				if(stackheight(stack)>stackheight(maxstack)){
					maxstack = stack;
				}
			}
		}
		
		if(bottom != null){
			maxstack.addFirst(bottom);
			map.put(bottom, maxstack);
		}
		return maxstack;
	}

	private static int stackheight(LinkedList<Box> stack) {
		// TODO Auto-generated method stub
		int height = 0;
		for(Box box:stack){
			height += box.height;
		}
		return height;
	}

	
}



class Box {
    int width;
    int height;
    int depth;
    
    Box(int width, int height, int depth) {
        this.width = width;
        this.height = height;
        this.depth = depth;
    }
    
    
    public String toString() {
        return "width: " + width + ", height: " + height + ", depth: " + depth;
    }
}