[LeetCode]Russian Doll Envelopes

这道题和Longest Increasing Subsequence是一样的，这道题找最多的Russian Doll就是找sort之后后最长的递增序列，递增的标准是两个dimension都要大于之前的元素。同样我们也有两种方法。
第一种方法，我们用envelopes[i]表示输入数组的第i个元素，dp[i]来表示以第i个元素结尾的最长递增子序列的长度，那么我们有递推公式：

• dp[i] = max(dp[j]) + 1, where envelopes[i].first > envelopes[j].first && envelopes[i].second > envelopes[j].second

时间复杂度 O(n ^ 2)，空间复杂度O(n)，代码如下：

第二种方法，我们对envelopes按照x轴的从小到大sort，如果x轴大小相同，按照y轴大小递减地排序，这样做的目的是为了防止x轴大小相同的元素被考虑进相同的increasing  subsequence，比如[4, 500], [4, 600]，显然其不构成递增序列，所以我们先考虑[4,600]再考虑[4,500]的话，我们就不用担心这种问题了。用dp[i]表示长度为i的按y轴大小递增的子序列的结尾的最小值，同样对于每一个我们遇到的数envelopes[i]:

• 如果envelopes[i].second > dp.back()，dp.push_back(envelopes[i].second)
• 如果envelopes[i].second <= dp.back(), 代表我们可以让某个长度为k的递增序列的结尾的值更小。我们binary search找到envelopes[i].second对应的insert postion，如果dp中不存在envelopes[i].second，我们找大于envelopes[i].second的最小值dp[k]，这代表envelopes[i]可以和之前的dp[k - 1]组成结尾更小的长度为k的递增子序列；如果dp中已经存在envelopes[i].second，我们啥也不做。

值得注意的是我们binary search找insert position的时候，对于长度为len的数，我们可以从[0, len]开始搜而不是[0, len - 1]，跳出条件是lo >= hi，这样对于insert postion在array末尾的数我们可以handle地更加简洁。

时间复杂度O(n * log n)，空间复杂度O(k)，k为Longest Increasing Subsequence的长度，代码如下：