最长子序列问题

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
子序列。
300. 最长递增子序列

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums: return 0
        l = []
        for num in nums:
            if not l or num > l[-1]:
                l.append(num)
            elif l and l[-1]==num: continue
            else:
                left,right=0,len(l)-1
                while left<=right:
                    mid=left+(right-left)//2
                    if l[mid]<num:
                        left = mid+1
                    else:
                        right = mid-1
                l[left] = num
            # print(l)
        return len(l)

面试题 08.13. 堆箱子

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

输入使用数组[wi, di, hi]表示每个箱子。
面试题 08.13. 堆箱子

class Solution:
    def pileBox(self, box: List[List[int]]) -> int:
        n = len(box)
        if n==0: return 0
        box.sort()
        dp = [t[2] for t in box]
        for i in range(1,n):
            for j in range(i):
                if box[j][0] < box[i][0] and box[j][1] < box[i][1] and box[j][2] < box[i][2]:
                    dp[i] = max(dp[i], dp[j]+box[i][2])
        return max(dp)