1. 问题描述
LIS(Longest Increasing Subsequence，最长递增子序列)：给出一个序 列
a1 ,a2 ,a3 ,a4 ,a5 ,a6 ,a7 ....an，求它的一个子序列（设为s1 ,s2 ,...sn），使得这个 子序列满足这样的性质s1<s2<s3<...<sn，并且这个序列的长度最长
给出一串正整数，如下
125343
能找到最长的单调递增的子序列为
1234
2. 动态规划法
2.1 设计思路
设b[i]是在a[i]为单调递增子序列最后一个元素时，所得最长单调递增子序列 的长度为：
网络异常，图片无法展示
|
思路：
- 输入母串的长度
- 循环输入母串数组以及母串的状态数组并初始化
- 外层循环，从左往右遍历，记录待更新数组为
a[i]- 里层循环，遍历母串的左闭右开区间
[0,i)，找到比a[i]小且状态值最大的数，更新a[i]的状态数组b[i]- 用一个变量max记录状态数组
b[i]的最大值就是最大子序列的数量
2.2 图解算法
a数组存储原始数据
b数组存储对应最长上升子序列长度
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
2.3 算法实现
时间复杂度O(n^2)
空间复杂度：S(n)
importjava.util.Scanner; publicclassMain { publicstaticvoidmain(String[] args) { Scannerscanner=newScanner(System.in); intn; int []num; int []dp; while(scanner.hasNext()) { n=scanner.nextInt(); num=newint[n+1]; dp=newint[n+1]; //输入母串，初始化状态数组dpfor(inti=1;i<=n;++i) { num[i]=scanner.nextInt(); dp[i]=1; } //动态规划算法for(inti=1;i<=n;++i) { for(intj=1;j<=i-1;++j) { if(num[j]<num[i]) { dp[i]=Math.max(dp[j]+1, dp[i]); } } } //遍历找出dp数组中的最大值intmax=0; for(inti=1;i<=n;++i) { max=Math.max(max, dp[i]); } System.out.println(max); } scanner.close(); } }
usingnamespacestd; constintmaxn=1003, INF=0x7f7f7f7f; inta[maxn], f[maxn]; intn,ans=-INF; intmain() { //输入母串的长度scanf("%d", &n); //获取母串并初始化状态数组for(inti=1; i<=n; i++) { scanf("%d", &a[i]); f[i] =1; } //反转数组reverse(a+1,a+n+1); //两层循环，更新状态数组for(inti=1; i<=n; i++){ for(intj=1; j<i; j++){ if(a[j] <a[i]){ if(f[i]<f[j]+1){ f[i]=f[j]+1; } //f[i] = max(f[i], f[j]+1); } } } //记录最大的状态数组值，即最长上升子序列长度for(inti=1; i<=n; i++){ //cout<<f[i]<<" ";ans=max(ans, f[i]); } printf("%d\n", ans); return0; }
2.4 算法优化
2.4.1 优化分析
内层循环所作的操作是在区间a[1,i)找到比a[i]小且状态值最大的数，就是一个查找的过程，我们所熟知的二分查找的效率是O(logn)，可不可以用二分来优化这个内层循环呢？
维护两个数组
b数组记录当前的最长单调递增长度
c数组记录的是当前长度下最后一个元素的值（不是很好理解，下面详说）
我们所要做的操作就是依次遍历序列中后续元素，更新两个数组
2.4.2 具体步骤
- 遍历到元素
a[i]时，先逆序检查记录当前长度下最后一个元素的值的c数组，找到当前表中第一个小于a[i]的元素k，及其对应的长度为x（记录在b数组中）；然后新建一个长度为x+1值（表示要准备将a[i]加入到序列中，但是要满足下列条件）- 看b数组中是否存在
x+1这个值- 如果不存在，就b数组新加值为
x+1的项目，c数组中新加对应的值a[i]- 如果存在，则比较当前的
a[i]和c数组中对应位置的值，如果a[i]较小，则更新此值为a[i]
2.4.3 图解算法
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
通过一番分析发现，c数组始终是递增有序的，所以我们可以用二分查找找到小于a[i]的最大元素c[x]的后一个元素，与之比较大小，如果a[i]小就替换c[x+1]=a[i]
如果a[i]大于c数组的最后一个元素，就可以直接将a[i]添加在c数组的后面
分析这么多其实理解了就是两行话
要找到c数组中第一个大于a[i]的元素，然后更新它的值，如果第一个大于a[i]的元素是c数组的最后一个元素，就直接将a[i]添加在c数组的后面)
老师的ppt绕来绕去，看了我半天结果理解起来就这么简单，哎，感觉自己前面白分析了
2.4.4 代码实现
时间复杂度：O(nlogn)
importjava.util.ArrayList; importjava.util.Arrays; importjava.util.Scanner; publicclassMain { publicstaticvoidmain(String[] args) { Scannerscanner=newScanner(System.in); intn,cl; int []a; int []b; int []c; while(scanner.hasNext()) { n=scanner.nextInt(); a=newint[n+1]; b=newint[n+1]; c=newint[n+1]; for(inti=1;i<=n;++i) { a[i]=scanner.nextInt(); } b[1]=1;c[1]=a[1]; cl=1; for(inti=1;i<=n;++i) { //如果第一个大于a[i]的元素是c数组的最后一个元素//就直接将a[i]添加在c数组的后面)if(a[i]>c[cl]) { c[++cl]=a[i]; b[cl]=cl; }else { intlow=1,high=i; while(low<=high) { intmid=(low+high)/2; if(c[mid]<a[i]) {low=mid+1;} else {high=mid-1;} } //二分查找找到c数组中第一个大于a[i]的元素，然后更新它的值c[low]=a[i]; } } System.out.println(b[cl]); for(inti=1;i<=cl;++i) { System.out.print(c[i]); if(i!=cl)System.out.print(" "); } } } } #include<bits/stdc++.h>usingnamespacestd; intarr[1005]; intmain(){ intn; cin>>n; for(inti=0;i<n;i++) cin>>arr[i]; reverse(arr,arr+n); vector<int>stk; stk.push_back(arr[0]); for (inti=1; i<n; ++i) { if (arr[i] >stk.back()) stk.push_back(arr[i]); else//二分查找*lower_bound(stk.begin(), stk.end(), arr[i]) =arr[i]; } cout<<stk.size() <<endl; return0; }
