LIS 最长递增子序列问题

时间：2022-09-03 01:28:29

一，    最长递增子序列问题的描述

设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。

比如int* inp = {9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}；

二，解决：

1.用一个临时数组tmp保存这样一种状态：tmp[i]表示以i为终点的递增序列的长度；

比如inp = {3，2，5}那么tmp = {1, 1, 2}，其中tmp[2]=2表示包含i=2位（inp[2]=5）的LIS的个数，即序列{3,5}，个数为2；

2.假设已经知道了tmp[0]到tmp[n-1]，那我们如何通过tmp[0]到tmp[n-1]的状态求得tmp[n]的状态？

比如inp = {3，2，5}，已经求得tmp[0]=1,tmp[1]=1,怎么求tmp[2]？

如果i<2那，i就有可能在2为终点的LIS序列上，那以2为终点的递增序列的长度就至少是i的最长序列+1,那么就必须满足以下两个条件：

inp[i]<inp[n]          tmp[i]+1>tmp[n]

比如i=0时，inp[0]=3<inp[n]=5且tmp[0]+1=2>tmp[2]=1(tmp[i]初值都为1)；则赋值tmp[2] = tmp[0]+1=2；

继续比较i=1，此时inp[1]=2<inp[n]=5且tmp[1]+1=2不大于tmp[2]=2；

一直循环到n-1位为止！最后得到tmp = {1, 1, 2}；

其中tmp的最大元素即为LIS的最大长度！

3.我们如何输出LIS的所有的值呢？

其实我们只需要知道LIS中，每个元素的前面一位元素的位置即可:

比如tmp = {1, 1, 2}的最大值是2，该LIS最后一位元素出现在i=2位，如果我们保存inp[2]=5在LIS中前面的那个元素，以此类推，我们就能找到LIS中所有元素；

比如{3，2，5}的LIS是{3，5}或{2，5}，我们用另一个临时数组存储它前一位元素下标int arr = {-1,-1,0}，表示以inp[2]=5结尾的LIS，其前一位元素的小标是0，即inp[0]=3，这样就找到了{3，2，5}的LIS是{3，5}；

#include <stdlib.h>

#include <stdio.h>

#include <string.h>

#include <assert.h>

//求最长递增子序列;

//ret[i]存放包含第i位的LIS的元素个数；

//path用于保存最长递增子序列路径；path[i]存放包含第i位的LIS的前一位元素的下标；

int LIS(int* inp,int len,int* ret,int* path){

   assert(inp);

   if(len <= ) return;

   int i = ,max = ,maxpoint = ;

   for(;i<len;i++){

     ret[i] = ;

     path[i] = -;//初始值都-1，为了以后输出方便，初值0时和path[0]混淆；

     int j = ;

     for(;j<i;j++){

        if(inp[i] > inp[j] && ret[j]+ > ret[i]){

           ret[i] = ret[j] + ;

           path[i] = j;

        }

     }

     printf("ret[i] ==%d\n",ret[i]);

     if(ret[i] > max){

        max = ret[i];

        maxpoint = i;//ret中最大的那个元素的下标；

     }

   }

   return maxpoint;

}

//输出数组

void printinp(int* inp,int len){

   int i = ;

   for(;i<len;i++){

     printf("inp = %d\n",inp[i]);

   }

}

//输出LIS；LIS中-1表示：包含该位元素的LIS，其前面没有元素；

void printpath(int* inp,int* path,int key){

   for(;key>=;){

      printf("inp[%d]=%d\n",key ,inp[key]);

      if(key == ) break;//path[0]处会死循环，必须跳出

      key = path[key];

   }

}

int main(){

  int inp[] = {,,,,,,,,};

  int len = sizeof(inp)/sizeof(int);

  int ret[len];

  int path[len];

  int maxpoint = LIS(inp,len,ret,path);

  printpath(inp, path, maxpoint);

}

输出结果：

ret[i] ==

ret[i] ==

ret[i] ==

ret[i] ==

ret[i] ==

ret[i] ==

ret[i] ==

ret[i] ==

ret[i] ==

inp[]=

inp[]=

inp[]=

inp[]=

LIS结果是8 6 4 2，输出正确！

相关文章