LIS定义

一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).

 

求解方法

1.动态规划

状态设计：F[i]代表以A[i]结尾的LIS的长度

状态转移：F[i]=max{F[i],F[j]+1}(1<=j< i,A[j]< A[i])

边界处理：F[i]=1(1<=i<=n)

时间复杂度：O(n^2)

 

1 #include
     
       2 #include
      
        3 int dp[30010];///以s[i]结尾的最长上升子序列长度为1 4 int s[30010]; 5 using namespace std; 6 int main() 7 { 8     int n,i,j; 9     while(scanf("%d",&n)!=EOF)10     {11         int ans=0;12         for(i=0; i
       
        s[j])23                 {24                     dp[i]=max(dp[i],dp[j]+1);25                 }26             }27             ans=max(dp[i],ans);28         }29         printf("%d\n",ans);30     }31     return 0;32 }
       
      
     

 

二.贪心+二分

我们可以模拟一个stack，每次取栈顶元素和读到的元素做比较,如果大于栈顶元素则将它入栈；如果小于，则二分查找栈中的比它大的第1个数，并替换它。最长序列长度即为最后模拟的大小。

我们再举一个例子：有以下序列A[]=3 1 2 6 4 5 10 7，求LIS长度。

　　我们定义一个B[i]来储存可能的排序序列，len为LIS长度。我们依次把A[i]有序地放进B[i]里。（为了方便，i的范围就从1~n表示第i个数）

　　A[1]=3，把3放进B[1]，此时B[1]=3，此时len=1，最小末尾是3

　　A[2]=1，因为1比3小，所以可以把B[1]中的3替换为1，此时B[1]=1，此时len=1，最小末尾是1

　　A[3]=2，2大于1，就把2放进B[2]=2，此时B[]={1,2}，len=2

　　同理，A[4]=6，把6放进B[3]=6，B[]={1,2,6}，len=3

　　A[5]=4，4在2和6之间，比6小，可以把B[3]替换为4，B[]={1,2,4}，len=3

　　A[6]=5，B[4]=5，B[]={1,2,4,5}，len=4 

　　A[7]=10，B[5]=10，B[]={1,2,4,5,10}，len=5

　　A[8]=7，7在5和10之间，比10小，可以把B[5]替换为7，B[]={1,2,4,5,7}，len=5

　　最终我们得出LIS长度为5。但是，但是！！这里的1 2 4 5 7很明显并不是正确的最长上升子序列。是的，B序列并不表示最长上升子序列，它只表示相应最长子序列长度的排好序的最小序列。这有什么用呢？我们最后一步7替换10并没有增加最长子序列的长度，而这一步的意义，在于记录最小序列，代表了一种“最可能性”，或者可以说是增大了这个序列的“潜力”。假如后面还有两个数据8和9，那么B[6]将更新为8，B[7]将更新为9，len就变为7。读者可以自行体会它的作用。

　　因为在B中插入的数据是有序的，不需要移动，只需要替换，所以可以用二分查找插入的位置，那么插入n个数的时间复杂度为〇(logn)，这样我们会把这个求LIS长度的算法复杂度降为了〇(nlogn)。

 

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 int a[30010]; 6 int lis[30010];///表示长度为i的LIS结尾元素的最小值 7 int main() 8 { 9     int n,i,j,len,pos;10     while(scanf("%d",&n)!=EOF)11     {12         len=0;13         memset(lis,0,sizeof(lis));14         for(i=0;i
        
         lis[len])22             {23                 lis[++len]=a[i];24             }25             else26             {27                 pos=lower_bound(lis,lis+len,a[i])-lis;28                 lis[pos]=a[i];29             }30         }31         printf("%d\n",len+1);///len是从0开始的32     }33 }