最长上升子序列
题目描述
这是一个简单的动规板子题。
给出一个由
最长上升子序列是指,从原序列中按顺序取出一些数字排在一起,这些数字是逐渐增大的。
输入格式
第一行,一个整数
第二行有
输出格式
一个整数表示答案。
样例 #1
样例输入 #1
6
1 2 4 1 3 4
样例输出 #1
4
提示
分别取出
思路
首先,定义了一些基本变量和数组。n
是一个整数,表示序列的长度,a
是一个长度为 dp
是一个长度为 a[i]
结尾的最长上升子序列的长度。
从输入中读取序列的长度 n
,然后读取序列的每一个元素,存储在数组 a
中。
然后,进行动态规划。状态转移方程如下:
如果
其中,
dp[i]
表示以 a[i]
结尾的最长上升子序列的长度。对于每一个 i
,初始化 dp[i]
为 j
从 i - 1
,如果 a[j]
小于 a[i]
,则更新 dp[i]
为 max(dp[i], dp[j] + 1)
,这表示如果 a[j]
可以接在 a[i]
前面,那么更新以 a[i]
结尾的最长上升子序列的长度。
动态规划过程结束后,寻找 dp
数组中的最大值,这就是序列的最长上升子序列的长度,输出这个值。
AC代码
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;
const int N = 1e6 + 7;
int n;
int a[N];
ll dp[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(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);
}
}
}
ll ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, dp[i]);
}
cout << ans << "\n";
return 0;
}
版权声明:本文为博主作者:HEX9CF原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/qq_34988204/article/details/137348955