一.LIS问题
最长上升子序列（Longest Increasing Subsequence）
1.子串和子序列
（1）字符子串指的是字符串中连续的n个字符。
（2）字符子序列指的是字符串中不一定连续但先后顺序一致的n个字符，即可以去掉字符串中的部分字符，但不可改变其前后顺序。
2.问题求解
2.1 DP O(n^2)：
问题分析：
数组d[i]表示，以A[i]结尾的最长上升子序列的长度。
我们通过这种方式是无法求出最长上升子序列具体是什么，这点和最长公共子序列不同。
代码实现：
//LIS DP
#include <iostream>
using namespace std;
const int N=1e4+2;
int n,d[N],result=0;
long long a[N];
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
int j=i-1,flag=1;
while(j>=0){
if(a[j]<a[i]){
d[i]=d[j]+1;
flag=0;
break;
}
--j;
}
if(flag){
d[i]=1;
}
}
for(int i=0;i<n;i++){
if(result<d[i]){
result=d[i];
}
}
cout<<result;
return 0;
}2.2 贪心+二分 O(nlogn):
问题分析：
low [ i ]表示长度为i的序列结尾元素的最小值。
每扫描一个新的元素，我们需要判断a[i]与low[max]的大小，如果a[i]大于low[max]，则low[++max]=a[i]；如果a[i]小于low[max]，从max向前回溯，找到第一个a[i]小于low[j]的j值，low[j]=a[i]，重复上述操作，直至扫描完整个序列。
注意在回溯过程中，由于low [ i ]记录的是元素的最小值，那么low数组是一个有序数组，则可以利用二分查找，二分一次 low 数组的时间复杂度为O(logn)，所以总的时间复杂度是O(nlogn)。
代码实现：
//LIS 贪心+二分
#include <iostream>
using namespace std;
const int N=1e4+2;
long long a[N],low[N]={0};
int n,result=0;
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
if(a[i]>low[result]){
low[++result]=a[i];
}
else{
int end=result-1,first=1;
int mid=(first+end)/2;
while(first<=end){
mid=(first+end)/2;
if(a[i]>low[mid]){
first=mid+1;
}
else{
end=mid-1;
}
}
if(mid>1){
low[mid]=a[i];
}
}
}
cout<<result;
return 0;
}
注：
lower_bound()、upper_bound()、equal_range() 以及 binary_search() ，它们的底层实现采用的都是二分查找的方式，进行查找的数组需要有序，使用时均需 #include <algorithm>。
1） lower_bound() 不小于
当查找成功时，迭代器指向找到的元素；反之，如果查找失败，迭代器的指向和 last 迭代器相同。
语法格式：
//在 [first, last) 区域内查找不小于 val 的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
const T& val);
//在 [first, last) 区域内查找第一个不符合 comp 规则的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
const T& val, Compare comp);具体演示：
//lower_bound()
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int a[5]={1,2,3,4,5};
int *p=lower_bound(a, a+5, 3);
//从a数组找到第一个不小于3的元素
return 0;
}2）upper_bound() 大于
//查找[first, last)区域中第一个大于 val 的元素。
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
const T& val);
//查找[first, last)区域中第一个不符合 comp 规则的元素
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
const T& val, Compare comp);3）equal_range()
//找到 [first, last) 范围中所有等于 val 的元素
pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val);4）binary_search()
//查找 [first, last) 区域内是否包含 val
bool binary_search (ForwardIterator first, ForwardIterator last,
const T& val);
//根据 comp 指定的规则，查找 [first, last) 区域内是否包含 val
bool binary_search (ForwardIterator first, ForwardIterator last,
const T& val, Compare comp);使用lower_bound()完成二分查找：
//贪心+二分 lower_bound()实现
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N=1e4+10;
long long a[N],low[N]={0};
int result=0,n;
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
if(a[i]>low[result]){
low[++result]=a[i];
}
else{
long long *p=lower_bound(low, low+result, a[i]);
//找到第一个不小于a[i]的元素
*p=a[i];
}
}
cout<<result;
return 0;
}2.3
