最长不下降子序列LIS详解

本文主要是介绍最长不下降子序列LIS详解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最长不下降子序列指的是在一个数字序列中，找到一个最长的子序列（可以不连续），使得这个子序列是不下降（非递减）的。

假如，现有序列A=[1，2，3，-1，-2，7，9]（下标从1开始），它的最长不下降子序列是[1,2,3,7,9]，长度为5。另外，还有一些子序列是不下降子序列，比如[1,2,3]、[-2,7,9]等，但是都不是最长的。

对于这个问题可以用最原始的方法枚举每一种情况，但是时间复杂度太高。

使用动态规划求解，令dp[i]表示以A[i]结尾的最长不下降子序列长度，这样对A[i]有两种可能：

（1）如果存在A[i]之前的元素A[j](j<i)，使得A[j]<=A[i]且dp[j]+1>dp[i]（即把A[i]跟在以A[j]结尾的LIS后面时能比当前以A[i]结尾的LIS长度更长），那么就把A[i]跟在以A[j]结尾的LIS后面，形成一条更长的不下降子序列（令dp[i]=dp[j]+1）。

（2）如果A[i]之前的元素都比A[i]大，那么A[i]就只好自己形成一条LIS，但是长度为1，即这个子序列里面只有一个A[i]。

最后以A[i]结尾的LIS长度就是（1）（2）中能形成的最大长度。

由此可以写出状态转移方程：

$dp[i]=max\left ( 1,dp[j]+1 \right )$

上面的状态转移方程隐含了边界：dp[i]=1，因此只要让i从小到大遍历即可求出整个dp数组。由于dp[i]表示的是以A[i]结尾的LIS长度，因此从整个dp数组中找出最大的那个才是要寻求的整个序列的LIS长度，整体复杂度为 $O\left ( n^{2} \right )$

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100;
int A[N],dp[N];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>A[i];}int ans=-1;for(int i=1;i<=n;i++){dp[i]=1;//初始条件（即先假设每个元素自成一个子序列） for(int j=1;j<i;j++){if(A[i]>=A[j]&&(dp[j]+1>dp[i])){dp[i]=dp[j]+1;}}ans=max(ans,dp[i]);}cout<<ans;return 0;
}

这篇关于最长不下降子序列LIS详解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！