最长不下降子序列（LIS）

一：最长不下降子序列状态转移方程：

                                f[i]=max(f[(0--i-1)]+1,f[i])
                            //f[i]指以i结尾的的最长不下降子序列的最长长度

二:具体思路:
正确思路：遍历每一个元素，求出以当前元素为结尾最长不下降子序列长度，最后求出其中的最大值
【即当前元素接到前面哪一个元素后面所构成的最长不下降子序列长度最大】
具体解析：
a.每个元素以它本身为结尾的最长不下降子序列长度至少为1（随输入赋值）
b.用一个大循环遍历每一个元素(设遍历到的当前元素为第i个元素)，其中嵌套一个小循环完成遍历从0到i-1的元
素，查看当前元素（a[i]）能够接在前面那一个元素之后构成不下降子序列，还要求出其中最大值（即接在哪一个元素之后的不下降子序
长度最大）从而找出以此元素结尾的最长不下降子序列的长度。

三：代码解析：

#include<iostream>
using namespace std;
int k;//k为最长不下降子序列的长度 
int max(int a,int b) 
{
    if(a>b)
        return a;
    else return b;
}
int main() {
    int n;//序列的元素个数 
    cin>>n;
    int a[n];
    int f[n];//表示以i结尾的最长不下降子序列的长度 
    for(int i=0; i<n; i++) {
        cin>>a[i];
        f[i]=1;//每个数字以它本身结尾的最长不下降子序列长度最少是1 
    }
    for(int i=1; i<n; i++)//分别遍历每个元素进而求出以各个元素结尾的最长不下降子序列的长度 
     {
        for(int j=0; j<=i; j++)//从第一个元素到当前元素一一遍历查看该元素能够加在哪一个f[i]之后 
            if(a[i]>a[j])//判断是否满足“不下降”的条件 
                f[i]=max(f[j]+1,f[i]);//取满足条件的最优值作为以当前元素为结尾的最长不下降子序列的长度 
    }
    for(int i=0; i<n; i++)
        k=max(f[i],k);//比较元素，找出最大值 
    cout<<k;
    return 0;
}

四：易错点：
1.只判断当前元素是否满足不下降的条件，从而忽视要求以当前元素为结尾的最大的长度作为其长度(第23行代码)，简单来说就是一定需要比较当前元素接到前面那一个值后面时，子序列长度最大，作为以当前元素为结尾的最长不下降子序列长度
【因为是一一遍历，所以要求最大值需要进行比较是当前遍历时（接到当前元素后）的值大，还是其中存储的原值大】
2.误以为以最后一个元素为结尾的最长不下降子序列长度就是整个序列的最长不下降子序列长度
【万一最后一个元素是序列中最小的一个咋办】

五：进程图：