(iBus的输入法真的难用啊。。。用起来的感觉就像被电脑和键盘cj/(ㄒoㄒ)/~~，写到一半忍不住去换了fcitx+搜狗，然而可能是我的使用姿势不对，总出BUG，不过现在终于对上号了owo~)
这个问题让我想了N久N久N久，深深地感到智商欠费怀疑人生，我真是应该自挂东南枝。。
问题：给出一个序列 例如(2 1 5 3 6 4 8 9 7)，求该序列的最长上升子序列长度(1 3 4 8 9，长度为5)。
最长上升子序列问题，常用解法有两种，都用到了动态规划的思想，一种是直接用动态规划，比较好想，但是算法复杂度为O(n^2)，另一种算法进行了优化，把时间复杂度降低到了O(nlogn)，此两种方法本文都进行讲解，先看第一种
- 通称O(n^2)算法
设a为存储序列的数组，设f[i]为以i结尾的最长子序列的长度，那么如何递推出f[i]的值呢？我们设一个变量j来表示，1<=j<=i-1，对于所有的a[j]，只有当a[j]<a[i]的时候，我们才需要判断是否需要把a[i]添加到f[j]中，当然我们需要注意，f[i]的以i结尾的最长子序列的长度，所以我们要在所有可以添加a[i]的子序列中，找到最长的那个子序列，然后我们把a[i]添加进子序列中，另f[i]=f[j]+1即可。
我在某篇博客上看到了f[i]=max(f[j](0<=j<i))+(a[i]>a[j]?1:0) 这样的公式，仔细研究这个公式其实是有BUG的，因为他找到的子序列max(dp[j])不一定能满足a[i]可以被添加进去，这点要注意仔细思考，不然很容易就出错。
正确的推理公式应该是:f[i]=max( f[j] | (1<=j<=i-1,a[i]>a[j]) ) + 1
我觉得这个算法是达不到O(n^2)的复杂度的。
代码：
int lis1(int a[],int n)
{
int *f=new int[n+1];
for(int i=0;i<=n;i++){f[i]=0;}//初始化
int Max;
for (int i = 1; i <= n; ++i){
Max = 0;
for (int j = 1; j <= i-1; ++j){
if (a[i] > a[j]){
Max = max(Max, f[j]);//找到可以把a[i]作为结尾的最长子序列
}
}
f[i] = Max + 1;//把a[i]加入到这个子序列中
}
Max = 0;
for (int i = 1; i <= n; ++i){//找到最长上升子序列
if (f[i] > Max) Max = f[i];
}
return Max;
}
- O(nlogn算法)
分析上面的算法发现，每次都要从i-1个数里面遍历，再找到最长的子序列，这就提高了计算时间，那么如何优化呢？是否有一种办法把这个寻找的过程简化？
我们使用b[i]来记录长度为i的上升子序列的末尾元素的最低值 ，这是什么意思？长度为i的子序列可能有很多个，而我们为了寻找整个序列的最长上升序列，只需要关注长度为i的序列末尾元素的最低值，因为末尾元素的值越低，我们越可能得到更长的上升子序列，这是一种贪心算法的思想，显然b数组的递增的。用反证法简单地证明一下，假若存在i<j，b[i]=a，b[j]=b，且a>b，那么长度为j的上升序列里面一定包含一个长度为i的子上升序列，且b[i]<b[j]，与假设矛盾。
我们假设b最开始是没有长度的，通过依次读取每一个a[i]来更新b的长度以及b数组中存储的值。
当我们读取到的a[i] 大于当前最长子序列的末尾元素最低值，那么a[i]可以被加入到这个子序列中，我们把当前最长子序列长度+1，并且更新b数组的值。
如果条件不成立，那么我们无法添加a[i]到当前最长的子序列中，这时候我们用a[i]更新长度不是最长的子序列末尾元素的最低值，如何更新呢，我们在b数组中从前向后找到 第一个大于a[i]的数，然后用a[i]去更新这个值，这是什么诡异操作？假如b[1-5]=1 3 4 6 9,a[i]=5，那么a[i]可以加入的子序列就只有b[1-3]=1 3 4，不过我们既然要求最长子序列，那就让a[i]并入长度为3的子序列，并入后长度为4，这时我们要更新b[4]的值，忘记b存储的是什么了嘛？是长度为i的上升子序列的末尾元素的最低值，a[i]是小于原来的b[4]的，所以把a[i]并入长度为3的子序列之后及时用a[i]更新b[4]的值。
如果对这里的操作还不是很明白的话，可以自己模拟一遍，在纸上写一写画一画～也可以点击这个链接：https://www.felix021.com/blog/read.php?1587 ，看一遍他的模拟过程。
下面放代码：
int lis2(int a[],int n){
int ans=0;//假设b最开始的长度为0
int *b=new int[n+1];
for(int i=0;i<=n;i++){b[i]=0;}//初始化b的值
for(int i=1;i<=n;i++){//依次读取a[i]的值并更新数组b
if(b[ans]<a[i]){//如果可以被添加到长度为ans的子序列里面
b[++ans]=a[i];//添加并且ans++;
continue;
}else{
b[insert_x(b,ans,a[i])]=a[i];//否则就使用a[i]更新b数组的值
}
}
delete []b;
return ans;//最后数组的长度ans就是答案。
}
int insert_x(int b[],int n,int x){//寻找插入点，插入第一个大于x的位置，b是数组，查找范围是[0,n]
int mid=0;
int front=0;
int rear=n;
while(front!=rear-1){//使用二分查找
mid=(front+rear)/2;
if(x>b[mid]){
front=mid;
}else{
rear=mid;
}
}
return front+1;
}
注意这个算法为什么比第一个算法快，因为b是递增的数列，所以查找插入点的时候可以使用二分查找，二分查找的速度远远快于遍历整个数组，所以，这就体现了数据结构对算法的重要程度。
下面贴一个完整可以运行的代码：
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
int lis1(int a[],int n);
int lis2(int a[],int n);
int insert_x(int b[],int n,int x);//在前N个数据里面，返回应该插入的位置
int main(){
int n=0;
cin>>n;
int *a=new int[n+1];
for(int i=1;i<=n;i++){
cin>>a[i];
}
cout<<lis1(a,n)<<endl;
cout<<lis2(a,n)<<endl;
delete []a;
return 0;
}
int lis1(int a[],int n)
{
int *f=new int[n+1];
for(int i=0;i<=n;i++){f[i]=0;}//初始化
int Max;
for (int i = 1; i <= n; ++i){
Max = 0;
for (int j = 1; j <= i-1; ++j){
if (a[i] > a[j]){
Max = max(Max, f[j]);//找到可以把a[i]作为结尾的最长子序列
}
}
f[i] = Max + 1;//把a[i]加入到这个子序列中
}
Max = 0;
for (int i = 1; i <= n; ++i){//找到最长上升子序列
if (f[i] > Max) Max = f[i];
}
return Max;
}
int lis2(int a[],int n){
int ans=0;
int *b=new int[n+1];
for(int i=0;i<=n;i++){b[i]=0;}
for(int i=1;i<=n;i++){
if(b[ans]<a[i]){
b[++ans]=a[i];
continue;
}else{
b[insert_x(b,ans,a[i])]=a[i];
}
}
delete []b;
return ans;
}
int insert_x(int b[],int n,int x){
int mid=0;
int front=0;
int rear=n;
while(front!=rear-1){
mid=(front+rear)/2;
if(x>b[mid]){
front=mid;
}else{
rear=mid;
}
}
return front+1;
}
输入：第一行输入一个数字N，后面输入N个数字，使用tab、空格、回车进行间隔
输出：使用两个算法进行计算的最长上升子序列长度
样例：
输入：
9
2 1 5 3 6 4 8 9 7
输出：
5
5