以下为《最长上升子序列ppt》的无排版文字预览，完整格式请下载

下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。

线性DP (最长上升子序列）

题目：给定一个无序的整数数组，找出其中最长上升子序列(LIS)长度。

输入：【5,7,1,9,4,6,2,8,3】

输出：4

解析：最长上升子序列是【1,4,6,8】长度为4以5为结尾的lis:5

以7为结尾的lis:5 ,7

以1为结尾的lis:1

以9为结尾的lis:5,7,9

以4为结尾的lis:1,4

以6为结尾的lis:1,4,6

以2为结尾的lis:1,2

以8为结尾的lis:1,4,6,8

以3为结尾的lis:1,2,3

用一个F数组记录每次上升子序列的长度

状态变量：

F[i]:记录以a[i]为结尾的最长上升子序列的长度

初始条件： f[i]=1(每个元素构成一个子序列）

ij模拟：构建模型：a[1]…..a[j]…..a[i-1], a[i]….a[n]

F[j] F[i] 递推式 (a[i]>a[j]&&f[j]+1>f[i] 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 个元素

（2）小则替换：如果a[i]小于或等于b[len],就用a[i]替换掉b数组中第一个大于或等于a[i]的元素。

假设第一个大于a[i]的元素是b[j]，那么就用a[i]换掉b[j]后，会使得b[1....j]这个上升的子序列的结尾元素更小，对于一个上升的子序列，其尾元素越小，越有利于续接其他的元素，也就是越有可能变得更长。

len=1; b[1]=a[1]

动态跟新b数组

for( i=2;ib[len]

b[++len]=a[i];

else

{ j= find(a[i]);

b[j]=a[i];

}

}

printf(“%d\n”,len);

int find(int x)

{ //二分查找第一个大于或等于x的位置

int l=1,r=len,mid;

while( lb[mid]) l=mid+1;

else r=mid-1;

}

return l;

}

模拟：b数组存储的是最长上升子序列吗？[文章尾部最后300字内容到此结束,中间部分内容请查看底下的图片预览]

以上为《最长上升子序列ppt》的无排版文字预览，完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。