最长不下降子序列指的是在一个数字序列中,找到一个最长的子序列(可以不连续),使得这个子序列是不下降(非递减)的。
假如,现有序列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]=1,因此只要让i从小到大遍历即可求出整个dp数组。由于dp[i]表示的是以A[i]结尾的LIS长度,因此从整个dp数组中找出最大的那个才是要寻求的整个序列的LIS长度,整体复杂度为
#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;
}