测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

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. 输出长度。