👨‍🎓作者简介：一位喜欢写作，计科专业大二菜鸟一枚
🏡个人主页：starry陆离
🕒首发日期：2022年5月8日星期日
📚订阅专栏：算法分析与设计
如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦

最长上升子序列

• 1. 问题描述
• 2. 动态规划法
• • 2.1 设计思路
  • 2.2 图解算法
  • 2.3 算法实现
  • • 时间复杂度O(n^2)
  • 2.4 算法优化
  • • 2.4.1 优化分析
    • 2.4.2 具体步骤
    • 2.4.3 图解算法
    • 2.4.4 代码实现

1. 问题描述

LIS(Longest Increasing Subsequence，最长递增子序列)：给出一个序 列a1 ,a2 ,a3 ,a4 ,a5 ,a6 ,a7 ....an，求它的一个子序列（设为s1 ,s2 ,…sn），使得这个 子序列满足这样的性质s1<s2<s3<...<sn，并且这个序列的长度最长

给出一串正整数，如下

1 2 5 3 4 3

能找到最长的单调递增的子序列为

1 2 3 4 

2. 动态规划法

2.1 设计思路

设b[i]是在a[i]为单调递增子序列最后一个元素时，所得最长单调递增子序列 的长度为：

思路：

1. 输入母串的长度
2. 循环输入母串数组以及母串的状态数组并初始化
3. 外层循环，从左往右遍历，记录待更新数组为a[i]
4. 里层循环，遍历母串的左闭右开区间[0,i)，找到比a[i]小且状态值最大的数，更新a[i]的状态数组b[i]
5. 用一个变量max记录状态数组b[i]的最大值就是最大子序列的数量

2.2 图解算法

a数组存储原始数据

b数组存储对应最长上升子序列长度

2.3 算法实现

最长递增子序列

时间复杂度O(n^2)

空间复杂度：S(n)

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int n;int []num;int []dp;while(scanner.hasNext()) {n=scanner.nextInt();num=new int[n+1];dp=new int[n+1];//输入母串，初始化状态数组dpfor(int i=1;i<=n;++i) {num[i]=scanner.nextInt();dp[i]=1;}     //动态规划算法for(int i=1;i<=n;++i) {for(int j=1;j<=i-1;++j) {if(num[j]<num[i]) {dp[i]=Math.max(dp[j]+1, dp[i]);}}}     //遍历找出dp数组中的最大值int max=0;for(int i=1;i<=n;++i) {max=Math.max(max, dp[i]);}System.out.println(max);}scanner.close();}}

#include #include #include #include #include #include using namespace std;const int maxn = 1003, INF = 0x7f7f7f7f;int a[maxn], f[maxn];int n,ans = -INF;int main(){    //输入母串的长度    scanf("%d", &n);//获取母串并初始化状态数组    for(int i=1; i<=n; i++) { scanf("%d", &a[i]); f[i] = 1;    }    //反转数组    reverse(a+1,a+n+1);//两层循环，更新状态数组    for(int i=1; i<=n; i++){ for(int j=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(int i=1; i<=n; i++){ //cout<<f[i]<<" "; ans = max(ans, f[i]);    }    printf("%d\n", ans);    return 0;}

2.4 算法优化

2.4.1 优化分析

内层循环所作的操作是在区间a[1,i)找到比a[i]小且状态值最大的数，就是一个查找的过程，我们所熟知的二分查找的效率是O(logn)，可不可以用二分来优化这个内层循环呢？

维护两个数组

b数组记录当前的最长单调递增长度

c数组记录的是当前长度下最后一个元素的值（不是很好理解，下面详说）

我们所要做的操作就是依次遍历序列中后续元素，更新两个数组

2.4.2 具体步骤

1. 遍历到元素a[i]时，先逆序检查记录当前长度下最后一个元素的值的c数组，找到当前表中第一个小于a[i]的元素k，及其对应的长度为x（记录在b数组中）；然后新建一个长度为x+1值（表示要准备将a[i]加入到序列中，但是要满足下列条件）

2. 看b数组中是否存在x+1这个值

   1. 如果不存在，就b数组新加值为x+1的项目，c数组中新加对应的值a[i]
   2. 如果存在，则比较当前的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)

import java.util.ArrayList;import java.util.Arrays;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int n,cl;int []a;int []b;int []c;while(scanner.hasNext()) {n=scanner.nextInt();a=new int[n+1];b=new int[n+1];c=new int[n+1];for(int i=1;i<=n;++i) {a[i]=scanner.nextInt();}b[1]=1;c[1]=a[1];cl=1;for(int i=1;i<=n;++i) {//如果第一个大于a[i]的元素是c数组的最后一个元素  //就直接将a[i]添加在c数组的后面)if(a[i]>c[cl]) {c[++cl]=a[i];b[cl]=cl;}else {int low=1,high=i;while(low<=high) {int mid=(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(int i=1;i<=cl;++i) {System.out.print(c[i]);if(i!=cl)System.out.print(" ");}}}}

#include using namespace std;int arr[1005];int main(){     int n;    cin>>n;    for(int i=0;i<n;i++) cin>>arr[i];    reverse(arr,arr+n);    vector<int>stk;    stk.push_back(arr[0]);    for (int i = 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;    return 0;}