最长上生子序列LIS

学习动态规划问题（DP问题）中，其中有一个知识点叫最长上升子序列（longest increasing subsequence），也可以叫最长非降序子序列，简称LIS。简单说一下自己的心得。

　　我们都知道，动态规划的一个特点就是当前解可以由上一个阶段的解推出，由此，把我们要求的问题简化成一个更小的子问题。子问题具有相同的求解方式，只不过是规模小了而已。最长上升子序列就符合这一特性。我们要求n个数的最长上升子序列，可以求前n-1个数的最长上升子序列，再跟第n个数进行判断。求前n-1个数的最长上升子序列，可以通过求前n-2个数的最长上升子序列……直到求前1个数的最长上升子序列，此时LIS当然为1。

　　让我们举个例子：求 2 7 1 5 6 4 3 8 9 的最长上升子序列。我们定义d(i) (i∈[1,n])来表示前i个数以A[i]结尾的最长上升子序列长度。

　　前1个数 d(1)=1 子序列为2；

　　前2个数 7前面有2小于7 d(2)=d(1)+1=2 子序列为2 7

　　前3个数在1前面没有比1更小的，1自身组成长度为1的子序列 d(3)=1 子序列为1

　　前4个数 5前面有2小于5 d(4)=d(1)+1=2 子序列为2 5

　　前5个数 6前面有2 5小于6 d(5)=d(4)+1=3 子序列为2 5 6

　　前6个数 4前面有2小于4 d(6)=d(1)+1=2 子序列为2 4

　　前7个数 3前面有2小于3 d(3)=d(1)+1=2 子序列为2 3

　　前8个数 8前面有2 5 6小于8 d(8)=d(5)+1=4 子序列为2 5 6 8

　　前9个数 9前面有2 5 6 8小于9 d(9)=d(8)+1=5 子序列为2 5 6 8 9

　　d(i)=max{d(1),d(2),……,d(i)} 我们可以看出这9个数的LIS为d(9)=5

　　总结一下，d(i)就是找以A[i]结尾的，在A[i]之前的最长上升子序列+1，当A[i]之前没有比A[i]更小的数时，d(i)=1。所有的d(i)里面最大的那个就是最长上升子序列。话不多说，show me the code！下面是代码实现的算法。

状态转移方程:朴素dp，记f(i)为记a[i]结尾的最长上升子序列

　　　　　　　　f(i)=max(f(j)+1) 1=<j<i ，初始化dp数组全为1，从1开始循环k，一旦小于a[i]状态转移，否则保留初始化的1——即之后所有值都比他小。O(n)=n^2

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstdlib>

 #include <cstring>

 #include <cmath>

 using namespace std;

 const int maxn = ,INF=0x7f7f7f7f;

 int a[maxn],f[maxn];

 int n,ans=-INF;

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

     {

         scanf("%d",&a[i]);

         f[i]=;

     }

     for(int i=;i<=n;i++)

         for(int j=;j<i;j++)

             if(a[j]<a[i]) f[i]=max(f[i],f[j]+);

     for(int i=;i<=n;i++)

         ans=max(ans,f[i]);

     printf("%d\n",ans);

     return ;

 }

巴特西

最长上生子序列LIS

最新文章

热门文章