包含指定元素的最长上升序列

题目要求：给出一个长度为N整数序列,请求出它的包含第K个元素的最长上升子序列。
很明显，可以求出1~(K-1)中小于v[K]的元素构成的LIS的长度l1,再求出(K+1)~N中大于v[K]的元素构成的LIS的长度l2,l1+l2+1即为包含第K个元素的LIS的长度。

求解LIS的nlogn算法可以参考本人的最长不上升子序列 。

需要注意的是，本题要求的是严格上升序列的长度，即序列中不能存在值相等的元素。
因此对于某个值v,只有在v严格大于S[top]才可以S[++top]=v.
若小于等于S[top],则要在S中找大于等于v的S[t]，而不是大于v的。否则求出来的可能是最长不下降序列。

代码如下

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN (200000+10)

long N,K;
long v[MAXN];
long ans1,ans2;
long tmp[MAXN],len;

void init()
{
   scanf("%ld%ld\n",&N,&K);
   long i;
   for(i = 1;i <= N;i ++)
       scanf("%ld",&v[i]);
}

long lis()   //计算tmp中的LIS
{
   static long S[MAXN];
   long top = 1;
   S[top] = tmp[0];
   long l,r,mid,i;
   fprintf(stderr,"len %ld\n",len);
   for(i = 1;i < len;i ++)
   {
       if(tmp[i] > S[top])
           S[++top] = tmp[i];
       else
       {
           l = 1;
           r = top;
           while(l < r)
           {
               mid = (l + r) / 2;
               if(S[mid] >= tmp[i])
                   r = mid;
               else
                   l = mid + 1;
           }
           S[l] = tmp[i];
       }
   }
   return top;
}

void solve()
{
   long i;
   len = 0;
   for(i = 1;i < K;i ++)
       if(v[i] < v[K])    tmp[len ++] = v[i];
   if(len > 0)
       ans1 = lis();
   else
       ans1 = 0;
   len = 0;
   for(i = K + 1;i <= N;i ++)
       if(v[i] > v[K])    tmp[len ++] = v[i];
   if(len > 0)
       ans2 = lis();
   else
       ans2 = 0;
   printf("%ld\n",ans1 + 1 + ans2);
}

int main()
{
   freopen("lis.in","r",stdin);
   freopen("lis.out","w",stdout);
   init();
   solve();
   fclose(stdout);
   return 0;
}