程序员面试金典-面试题 08.13. 堆箱子

题目：

堆箱子。给你一堆n个箱子，箱子宽 wi、高hi、深di。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。

输入使用数组[wi, di, hi]表示每个箱子。

示例1:

输入：box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]
输出：6
示例2:

输入：box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]]
输出：10
提示:

箱子的数目不大于3000个。

分析：

把箱子按宽进行升序排序，然后求复合条件的最大上升子序列。当然这里上升要符合宽高深的要求。

程序：

class Solution {
    public int pileBox(int[][] box) {
        int[] res = new int[box.length];
        Arrays.sort(box, (a, b) -> a[0] - b[0]);
        for(int i = 0; i < box.length; ++i)
            res[i] = box[i][2];
        for(int i = 1; i < box.length; ++i){
            for(int j = 0; j < i; ++j){
                if(box[j][0] < box[i][0] && box[j][1] < box[i][1] && box[j][2] < box[i][2]){
                    res[i] = Math.max(res[i], res[j] + box[i][2]);
                }
            }
        }
        int longest = 0;
        for(int l : res)
            if(longest < l)
                longest = l;
        return longest;
    }
}