最长不下降序列(LIS)详解

本文同时发布在: CSDN - WillHou 的博客

题目描述就不写了，这题实在太经典了。

下面重点分析算法：

大家都知道，这题是一道动态规划的入门题。众所周知，动态规划的题都可以通过搜索来骗分获得一定的分数。所以，对于这道题，我们仍然可以先用$dfsdfs$写出来。代码较为暴力好懂，就不做解释。这个代码可以获得40-60分(视不同的OJ而定)

#include <iostream>
#include <cstring>
const int N = 109;
int n = 1, mx = -1, a[N], ans[N], anss[N];
void dfs(int x, int cnt)
{
    if (x > n)
        return ;
    if (cnt > mx)
    {
        mx = cnt;
        memcpy(anss, ans, N);
        // printf("mx=%d\n", mx);
        // for (int i = 1; i <= mx; i++)
        //     printf("%d ", ans[i]);
        // puts("");
        // puts("----------");
        // 这个注释可供大家看看这个程序的处理过程，以便小白更好的理解这段代码
    }
    for (int i = x; i <= n; i++)
        if (a[i] > ans[cnt])
        {
            ans[++cnt] = a[i];
            dfs(i+1, cnt);
            ans[cnt--] = 0;
        }
}
int main()
{
    while (~scanf("%d", a + n)) n++; n--;
    dfs(1, 0);
    printf("%d\n", mx);
    for (int i = 1; i <= mx; i++)
        printf("%d ", anss[i]);
    return 0;
}

测试样例：

第一步. 确定状态

通常处理数列的题目, 我们都有现成的状态划分, 即从第一个数开始, 到第$nn$个数结束.

这时候有个问题: 第$ii$个数我到底是取它还是舍它? 如果不包含$ii$, 那就没法写出状态转移方程.

不妨改成:

第二步. 状态转移方程

为了方便描述, 我们将输入定为为$aa$数组, 储存动态规划结果数组定义为$ff$数组

根据状态, 我们推导出状态转移方程: $f[i]=max(f[j])+1f[i]=max(f[j])+1$, 其中. 原因可以通过图示来说明.

易得$f[1]=1f[1]=1$, 因为它独立成为一个最长不下降子序列

因为, 所以不存在.

此时, 存在, 所以$mx=f[2]=1mx=f[2]=1$. $f[3]=mx+1=2f[3]=mx+1=2$.

此时, 存在, 所以$mx=max(f[2],f[3])=f[3]=2mx=max(f[2],f[3])=f[3]=2$. $f[4]=mx+1=3f[4]=mx+1=3$

以此类推... 直至算到$f[14]f[14]$, 结束循环. 此时, max{f[i]}即为答案.

因此, 有以下代码:

#include <iostream>
const int N = 109;
int n = 1, ans, a[N], f[N];
int main()
{
    while (~scanf("%d", a + n)) n++; n--;
    for (int i = 1; i <= n; i++)
    {
        int mx = 0, id = 0;
        for (int j = 1; j < i; j++)
            if (a[j]<a[i] and mx<f[j])
                mx = f[j];
        f[i] = mx + 1;
        if (f[i] > ans)
            ans = f[i];
    }
    printf("%d\n", ans);
    return 0;
}

部分OJ还要求输出最长不下降序列. 这似乎很难写, 实际上我们只需要加一个数组和一个变量就可以搞定.

为了方便描述, 我们将元素$ii$的前驱定为$pre[i]pre[i]$.

找出所有满足的$jj$. 求出max{a[j]}的下标$idid$, 那么记录$pre[i]=idpre[i]=id$. 可以通过图示来帮助更好的理解.

$pre[1]pre[1]$没有前驱, 故$pre[1]=0pre[1]=0$.

$77$之前没有比它大的, 所以$pre[2]=0pre[2]=0$.

$99$之前有, 所以$pre[3]=max\{a[j]\}\mathrm{的}\mathrm{下}\mathrm{标}=a[2]\mathrm{的}\mathrm{下}\mathrm{标}=2pre[3]=max\backslash \{a[j]\backslash \}的下标=a[2]的下标=2$.

$1616$之前有, 所以$pre[4]=max\{a[j]\}\mathrm{的}\mathrm{下}\mathrm{标}=a[3]\mathrm{的}\mathrm{下}\mathrm{标}=3pre[4]=max\backslash \{a[j]\backslash \}的下标=a[3]的下标=3$.

以此类推... 直至$pre[14]pre[14]$, 然后递归$print(pre[max\{f[i]\mathrm{的}\mathrm{下}\mathrm{标}\}])print(pre[max\backslash \{f[i]的下标\backslash \}])$, 直至$x=0x=0$结束输出.

因此, 有如下代码: (代码中的$sidsid$即上文分析中的$idid$)

#include <iostream>
const int N = 109;
int n = 1, ans, sid, a[N], f[N], pre[N];
void print(int x)
{
    if (x == 0)
        return ;
    print(pre[x]);
    printf("%d ", a[x]);
}
int main()
{
    while (~scanf("%d", a + n)) n++; n--;
    for (int i = 1; i <= n; i++)
    {
        int mx = 0, id = 0;
        for (int j = 1; j < i; j++)
            if (a[j]<a[i] and mx<f[j])
                mx = f[j], id = j;
        f[i] = mx + 1, pre[i] = id;
        if (f[i] > ans)
        {
            ans = f[i];
            sid = i;
        }
    }
    printf("%d\n", ans);
    print(sid);
    return 0;
}