(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

      快速幂取模，是指求(a^n)%m , a和n都非常的大，如果直接计算a^n可能直接溢出，在这种情况下取模，需要用到同余定理的一些推论。

关于同余定理，可以看这里，注意幂运算部分，“幂运算：如果a ≡ b (mod m)，那么a^n ≡ b^n (mod m)“ ，若a、b取m同余，则a^n、b^n关于m同余，注意a与a%m是同余的，所以把b替换为a%m，得a^n ≡ (a%m)^n (mod m)，即(a^n)%m=((a%m)^n)%m快速幂取模就是运用了这个公式，把a^n拆开运算。

• 先来看直接运用这个公式。

         直接运用就是直接把aaaa……拆开，拆成(a%m)(a%m)(a%m)(a%m)……然后再取模，上代码

long long solve(int a, int n, int m) {求a^n的模
    long long ans = 1;
    a = a%m;//先取一次模把数变小，a%m%m=a%m
    for (int i = 1; i <= n; i++) {
        ans = ans*(a%m);
    }
    return ans%m;
}

注意到这里展开就变成了(a%m)(a%m)(a%m)*(a%m)，值得警惕的是，当m和n比较大，还是有很大的可能会溢出，因为要连乘法n次，于是有了第二种写法。

long long solve(int a, int n, int m) {求a^n的模
    long long ans = 1;
    a = a%m;//先取一次模把数变小，a%m%m=a%m
    for (int i = 1; i <= n; i++) {
        ans = (ans*a)%m;
    }
    return ans%m;
}

只改动了代码的第5行，改动后展开变成了((((a%m)a)%ma)%ma)%m……稍微推一下就可以推出这个式子和上面的(a%m)(a%m)(a%m)(a%m)……是同余的，那这样写有什么好处呢，好处就是降低了溢出的可能性，每次*a后都要%m,相当于每次都把结果控制在了0~m-1的范围内，大大减小了溢出的可能性。所以这种写法是比第一种要更安全的。

但是这两种方法都有一个问题，那就是，时间复杂度为O(N)，每次都要乘啊，这么写代码，难道计算机不会痛嘛！于是就有了第二种算法，快速幂取模。

• 快速幂取模

         快速幂取模，是一种二分的思想，怎么说呢，举个栗子吧，6^16==36^8==(66)^8，怎么运用这个来快速取模呢，(6^16)%m=((66)^8)%m={[(66)^4][(6*6)^4]}%m,看起来好不方便，那我们直接上代码吧

ps：如果是6^17次方呢？怎么二分，答案是，我们先提出来一个6变成(66^16)%m==((6%m)(6^16%m))%m，这样就可以正常运算了。

long long solve(long long a, long long n, long long m)
{
    long long ans = 1;
    a = a % mode;
    while (n > 0) {
        if (n % 2 == 1) //判断是否是奇数，也可以使用&符合判断是否为奇数
            ans = (ans * a) % m; 
        a = (a * a) % m;// 不断的两两合并再取模
                n /= 2;//这里可以使用位运算 n>>=1 来除以2，使用位操作运算速度更快。
    }
    return ans%m;

让我们随便带个数进去看看~假若a是6，n是16，即求(6^16)%，在这个算法中会怎么走呢？

n=16;

a=6%m;

进入循环:

    a=( (6%m) * (6%m) )%m;// 即(6*6)%m  运用了公式(a*b)≡(a%m)*(b%m)(mod m),这个公式是因为a与a%m同余，b与b%m同余，所以a*b与a%m*b%m同余;

    n=8;

    a=(  (6*6)%m * (6*6)%m  )%m//即(6*6*6*6)%m

    n=4;

    a=(  (6*6*6*6)%m * (6*6*6*6)%m  )%m//即(6^8)%m;

    n=2;

    a=(6^16)%m;

    n=1;

    判断n是奇数，所以

    ans=(6^16)%m;

    后面对a的赋值已经没有比较管了，因为n/2=0会直接跳出循环，得到ans即为答案。

如果n是奇数会如何？假若a=6,n=17

n=17;

a=6%m;

进入循环:

    判断n(17)是奇数

    ans=6%m;

    a=( (6%m) * (6%m) )%m;// 即(6*6)%m  运用了公式(a*b)≡(a%m)*(b%m)(mod m);

    n=8;

    a=(  (6*6)%m * (6*6)%m  )%m//即(6*6*6*6)%m

    n=4;

    ……
可以看到，奇数的时候，程序先取出了一个6，然后剩下6^16正常处理
最后n=1时，ans = (ans * a) % m;会把第一个取出来的值也乘上去,
得到ans=(  (6%m) * ((6^16)%m)  )%m = (6^17)%m;即为所求

例题：

POJ1995

这题不仅用到了同余定理在乘法方面的推论，还用到了在加法方面的推论，堪称模板题。题解自行百度。