最长上升子序列 (LIS)问题详解

最长上升子序列 (LIS) 问题详解

在线提交地址请点击题目
请静下心来，认真阅读文字，若有任何疑问，欢迎留言 (*^_^*)

题目描述

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数N。
第二行包含N个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

输入样例

7
3 1 2 1 8 5 6

输出样例

4

数据范围

1 ≤ N ≤ 1000，
$-10^9$ ≤ 数列中的数 ≤ $10^9$

解题分析

首先，对 子序列 这个概念做下解释。子序列 是指原序列中选出一些数，在不该变原有顺序的条件下，所构成的序列。例如：原序列为 3 1 2 1 8 5 6，3 1 1 6是其子序列，1 2 5 6同样也是其子序列。子序列中的数 不要求 在原序列中紧密相连。

然后，我们对原问题进行拆分。由于需要准确地表示所拆出来的子问题，我们定义 $f[i]$ 为以下标是 $i$ 的数字做为子序列的结尾，所有合法子序列长度中的最大值。

如何计算出 $f[i]$ 呢？在动态规划问题中，求解未知的子问题时，常常通过已求解出的子问题的解来得到未求解出问题的解。

当我们在求解 $f[i]$ 时，已知的是所有下标 $j$ 在 $1\le j<i$ 范围内，以下标为 $j$ 结尾的子序列长度的最大值。 $f[i]$ 所能够转移到的状态需满足数字 $a[i]$ 大于数字 $a[j]$ 。

所以，$f[j]$ 应为所有能够转移的状态中，子序列的最长长度加 $1$ 。

可得到状态转移方程式：$f[i]=max(f[i],f[j]+1)(1\le j<i，a[j]<a[i])$ 。其中 $a$ 为原序列。

参考代码

希望各位读者能够在阅读代码前独立完成

#include <iostream>
#include <cstdio>

using namespace std;

int f[1010], a[1010], n;

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    for (int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for (int j = 1; j < i; j++)
            if (a[i] > a[j])
                f[i] = max(f[i], f[j] + 1);
    }

    int res = -1;
    for (int i = 1; i <= n; i++)
        res = max(res, f[i]);
        
    printf("%d", res);
    
    return 0;
}

本文从属于《动态规划入门指南》系列，更多动态规划问题的思维分析请点击链接查看。