本文共 2198 字，大约阅读时间需要 7 分钟。

问题描述

最长上升子序列(LIS):

给定长度为n的序列，从中选取一个子序列，这个子序列需要单调递增

问最长上升子序列(LIS)的长度

eg：1，5，2，3，11，7，9

则LIS序列为:1，2，3，7，9，长度为5

一.简单推论（非0 n情况）

1.问题分析

设计状态dp[x]为以a[x]结尾的LIS长度，那么整体的LIS长度就为dp数组的最大值。

以eg为例： a[n]为序列数组，dp[n]为LIS数组。 dp[1]=以a[1]，即以1结尾的LIS长度，即为1； dp[2]=以a[2]，即以5结尾的LIS长度，即为2； dp[3]=以a[3]，即以2结尾的LIS长度，这里我们注意到，2小于5，所以{1，5，2}的LIS长度=2，也就是dp[2],所以在a[3]<a[2]的情况下dp[3]=dp[2]; dp[4]=以a[4]，即以3结尾的LIS长度，这里我们注意到，3大于2，所以{1，5，2，3}的LIS长度=3，也就是dp[3]+1,所以在a[4]>a[3]的情况下dp[4]=dp[3]+1; dp[5]=以a[5]，即以11结尾的LIS长度，这里我们注意到，11大于3，所以{1，5，2，3，11}的LIS长度=4，也就是dp[4]+1,所以在a[5]>a[4]的情况下dp[5]=dp[4]+1; dp[6]=以a[6]，即以7结尾的LIS长度，这里我们注意到，7小于11，所以{1，5，2，3，11，7}的LIS长度=4，也就是dp[5],所以在a[6]<a[5]的情况下dp[6]=dp[5]; dp[7]=以a[7]，即9结尾的LIS长度，这里我们注意到，9大于7，所以{1，5，2，3，11，7，9}的LIS长度=5，也就是dp[6]+1,所以在a[7]>a[6]的情况下dp[7]=dp[6]+1; 根据以上推导，我们就得到了dp数组{1，2，2，3，4，4，5}，dp数组的最大值5即我们所求的a数组的LIS长度。

2.状态转移方程

3.参考代码

#include
   
    using namespace std;int main(){
       int n;    cin>>n;    int a[n+1],dp[n+1];    a[0]=0,dp[0]=0;    for(int i=1;i<=n;i++)cin>>a[i];    for(int i=1;i<=n;i++)    {
           dp[i]=1;        if(a[i]>a[i-1])dp[i]=dp[i-1]+1;        else dp[i]=dp[i-1];    }    int maxdp=1;    for(int i=1;i<=n;i++)    {
           maxdp=max(maxdp,dp[i]);    }    cout<
   

4.运行结果

二.严谨推论

1.问题分析

设计状态dp[x]为以a[x]结尾的LIS长度，那么整体的LIS长度就为dp数组的最大值。在求dp[x]的时候考虑比a[x]小的每一个a[i]的dp[i]+1。

以eg为例： a[n]为序列数组，dp[n]为LIS数组。 dp[1]=以a[1]，即以1结尾的LIS长度，即为1； dp[2]=以a[2]，即以5结尾的LIS长度，即为2； dp[3]=以a[3]，即以2结尾的LIS长度，这里我们注意到，2小于5，2大于1，所以{1，5，2}的LIS长度=2，也就是dp[1]+1,所以在a[2]>a[1]的情况下dp[3]=dp[1]+1; dp[4]=以a[4]，即以3结尾的LIS长度，这里我们注意到，3大于2，3大于1，所以{1，5，2，3}的LIS长度=3，也就是max(dp[1],dp[2])+1,所以在a[4]>a[3]，a[4]>a[1]的情况下dp[4]=max(dp[1],dp[2])+1； dp[5]=以a[5]，即以11结尾的LIS长度，这里我们注意到，11大于3，11大于2，11大于5，11大于1，所以{1，5，2，3，11}的LIS长度=4，也就是max{dp[1],dp[2],dp[3],dp[4]}+1,所以在a[5]>a[4]，a[5]>a[3]，a[5]>a[2]，a[5]>a[1]的情况下dp[5]=max{dp[1],dp[2],dp[3],dp[4]}+1; 同理推导。。。。。。 根据以上推导，我们就得到了dp数组{1，2，2，3，4，4，5}，dp数组的最大值5即我们所求的a数组的LIS长度。

2.状态转移方程

3.参考代码

#include
   
    using namespace std;int main(){
       int n;    cin>>n;    int a[n+1],dp[n+1];    a[0]=0,dp[0]=0;    for(int i=1;i<=n;i++)cin>>a[i];    for(int i=1;i<=n;i++)    {
           dp[i]=1;        for(int j=1;j<=i;j++)        {
               if(a[j]
   

4.运行结果

转载地址：http://jbok.baihongyu.com/