最长上升子序列问题是一个比较重要的算法问题，建议掌握。
300. 最长上升子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18] 输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
- 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
- 你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
解题思想：动态规划、二分查找
难点在于二分查找，常规的遍历会超时。
方法一：二分查找
最长上升子序列一定是在同样长地子序列中尾部元素最小的！所以，当元素大于尾部元素时，序列长度加一。小于尾部元素时，替换尾部元素。保存有上升趋势地子序列及长度，长度只增不减，如果元素小于子序列内的元素，则替换。比较大小用的是二分法，对已搜索到的子序列进行查找替换。
i,j表示当前位置最长子序列地上下界。m表示中点。当前位置地数值与中间点比较，若是大于中间点，则i=m,进一步比较，如果比子序列的值都大，则子序列长度加一。如果小于当中的某个，则替换该值，序列长度不变。i表示num要替换地位置。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int l=nums.size();
if(l==0)
return 0;
int res=0,m;
int tails[l];
for(auto num:nums)
{
int i=0;int j=res;
while(i<j)
{
m=(i+j)/2;
if(tails[m]<num)
i=m+1;
else
j=m;
}
tails[i]=num;
if(i==res)
res++;
}
return res;
}
方法二：动态规划
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int l=nums.size();
if(l==0)
return 0;
//dp[i]表示以第i个元素结尾的最长子序列长度
vector<int> dp(l+1,0);
int m=0;
for(int i=1;i<l;i++)
{
for(int j=0;j<i;j++)
{
if(nums[i]>nums[j])
dp[i]=max(dp[i],dp[j]+1);
}
//取所有长度中的最大值
if(dp[i]>m)
m=dp[i];
}
return m+1;
}
};
二维LIS问题
面试题 17.08. 马戏团人塔
有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。
示例：
输入：height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110]
输出：6
解释：从上往下数，叠罗汉最多能叠 6 层：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)
提示：
height.length == weight.length <= 10000
- 这里先使用sort根据height从小到大排序，其中关键的是如果height相同则按照weight从大到小排序（注意一个是从小到大，一个是从大到小）。
这样安排是为了让后续的根据weight求最大上升子序列时不会选到height一样的数据，即让height相同的数据的weight从大到小排列，让它不满足上升序列的“上升”，这样就巧妙避开了重复选取，将身高相同的人看成1个集合。 - 最后就是根据weight值求最长上升子序列的长度，即leetcode300的方法。这里使用了STL函数lower_bound()代替二分查找来简化代码。
lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
在从小到大的排序数组中，
lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。
upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字。
在从大到小的排序数组中，
lower_bound( begin,end,num,greater<type>() ):二分查找第一个小于或等于num的数字。
upper_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字。
class Solution {
public:
static bool cmp(pair<int,int> a,pair<int,int> b)
{
if(a.first<b.first)
return true;
else if(a.first==b.first)
return a.second>b.second;
return false;
}
int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {
int l=height.size();
if(l==0)
return 0;
vector<pair<int,int>> pep;
vector<int> tails;
for(int i=0;i<l;i++)
{
pep.push_back({height[i],weight[i]});
}
sort(pep.begin(),pep.end(),cmp);
for(auto p:pep)
{
if(tails.empty()||p.second>tails.back())
tails.push_back(p.second);
else
{
auto pos=lower_bound(tails.begin(),tails.end(),p.second);
*pos=p.second;
}
}
return tails.size();
}
};
要注意的是，自定义比较函数如果在类中，应该定义为static，因为：sort中调用函数cmp，不用加对象名，就能直接访问函数。
354. 俄罗斯套娃信封问题
给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
说明:
不允许旋转信封。
示例:
输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]
class Solution {
public:
static bool cmp(vector<int> a, vector<int> b)
{
if(a[0]<b[0]) return true;
else if(a[0] == b[0]) return a[1] > b[1];
return false;
}
int maxEnvelopes(vector<vector<int>>& envelopes) {
int n=envelopes.size();
sort(envelopes.begin(),envelopes.end(), cmp);
vector<int> t;
for(int i=0;i<n;i++)
{
if(t.empty()||t.back()<envelopes[i][1])
t.push_back(envelopes[i][1]);
else
{
auto pos=lower_bound(t.begin(),t.end(),envelopes[i][1]);
*pos=envelopes[i][1];
}
}
return t.size();
}
};
二维数组的sort问题；&和，&是取地址，是是指针，向指定地址进行操作。
