A70701. 最长上升子序列LIS(2)
编程题
提高
知识点
题目描述
给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N 。
第二行包含 N 个整数,表示完整序列。
1≤N≤100000,−10^9≤ 数列中的数 ≤10^9
输出格式
输出一个整数,表示最大长度。
输入输出样例
输入 #1
6 1 3 2 8 5 6
输出 #1
4
说明/提示
## 思路
LIS:dp[i] 表示以 i 结尾的最长上升长度,转移为前面更小元素 +1。
## 步骤
1. 读入序列。
2. 双重循环或二分优化求 LIS。
3. 输出长度。
LIS:dp[i] 表示以 i 结尾的最长上升长度,转移为前面更小元素 +1。
## 步骤
1. 读入序列。
2. 双重循环或二分优化求 LIS。
3. 输出长度。