最长上升子序列问题讲解

1.概念解析

    最长上升子序列$（LongestIncreasingSubsequence，LIS）$，在计算机科学上是指一个序列中最长的单调递增的子序列。最长上升子序列问题，就是求出一个序列中这样的子序列的长度的问题（不要求一定连续）。

2.举例了解

    先来看看一组数据：

6
1 2 4 1 3 4

    请你求出其中最长上升子序列的长度。

    这是一道经典的动态规划例题，可以直接采用动态规划五步走。

1.明确问题：如题所述。
2.状态：dp[i]表示以i结尾的最长子序列的长度。
3.初始条件：dp[i]=1。
4.状态转移方程$$dp[i]=max(1,dp[j]+1)(j\in [1,i)且a[i]>a[j])$$
5.答案：$max(dp[i])$。

    首先，问题和状态不用过多解释。

    初始条件也很容易明白，每一个数自己可以构成一个序列，也就是$dp[i]$至少为$1$。

    接下来是状态转移方程。我们可以遍历i前面的所有数j。如果a[i]>a[j]，即第i个数比第j个数小，那么就可以把第i个数接到第j个数后面。长度就变为了dp[j]+1（把第i个数接到后面去了，所以要$+1$）。取其中的最大值就行了。

    最后是答案。很明显，最长上升子序列有可能是以任何数结尾的。在转移状态时，我们就可以将当前状态与ans取个较大值，具体请看程序示例。

    我们将上面的样例代入一下，得到这样的$dp$表：

数	1	2	4	1	3	4
$dp$数组中的值	1	2	3	1	3	4

    请读者认真理解，以加深印象。可以尝试自己编写程序。

3.示例程序

直接输出答案：

#include<bits/stdc++.h>
using namespace std;
#define MAXN 5010 //题目中n数据范围,可以按情况改动
int main(){
	int n, a[MAXN], dp[MAXN], ans = 0; //先给ans赋一个最小值
	cin >> n;
	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] < a[i]) //状态转移方程
		        dp[i] = max(dp[i], dp[j]+1);
		ans = max(ans, dp[i]); //答案
	}
	cout << ans;
	return 0;
}

输出表格：

#include<bits/stdc++.h>
using namespace std;
#define MAXN 5010 //题目中n数据范围,可以按情况改动
int main(){
	int n, a[MAXN], dp[MAXN];
	cin >> n;
	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] < a[i]) //状态转移方程
		        dp[i] = max(dp[i], dp[j]+1);
	}
	for (int i = 1; i <= n; i++)cout << dp[i] << " ";
	return 0;
}

纯净无注释版：

#include<bits/stdc++.h>
using namespace std;
#define MAXN 5010
int main(){
    int n, a[MAXN], dp[MAXN], ans = 0;
    cin >> n;
    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] < a[i])
                dp[i] = max(dp[i], dp[j]+1);
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
}

最长上升子序列

通往洛谷的传送门

题目描述

这是一个简单的动规板子题。

给出一个由 $n(n\le 5000)$ 个不超过 $10^6$ 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。

最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。

输入格式

第一行，一个整数 $n$，表示序列长度。

第二行有 $n$ 个整数，表示这个序列。

输出格式

一个整数表示答案。

输入输出样例

输入 #1

6
1 2 4 1 3 4

输出 #1

4

提示

分别取出 $1$、$2$、$3$、$4$ 即可。

思路解析

    直接照搬上面的代码就行了。

喜欢就订阅此专辑吧！

【蓝胖子编程教育简介】
蓝胖子编程教育，是一家面向青少年的编程教育平台。平台为全国青少年提供最专业的编程教育服务，包括提供最新最详细的编程相关资讯、最专业的竞赛指导、最合理的课程规划等。本平台利用趣味性和互动性强的教学方式，旨在激发孩子们对编程的兴趣，培养他们的逻辑思维能力和创造力，让孩子们在轻松愉快的氛围中掌握编程知识，为未来科技人才的培养奠定坚实基础。

欢迎扫码关注蓝胖子编程教育