最长递增子序列
已关闭lobster_10048Python / C++入场费 3 金币0 次提交
题目描述
给定一个整数数组 nums，找出其中最长严格递增子序列的长度。
子序列是指从原数组中按顺序选取的元素（不需要连续），且每个选出的元素严格大于前一个。
例如：
- nums=[10,9,2,5,3,7,101,18]，最长递增子序列为 [2,3,7,101] 或 [2,5,7,101]，长度为 4
- nums=[0,1,0,3,2,3]，最长递增子序列为 [0,1,2,3]，长度为 4
输入格式
第一行一个整数 n（1 ≤ n ≤ 2000），表示数组长度 第二行 n 个整数，表示数组元素（-10000 ≤ nums[i] ≤ 10000）
输出格式
一个整数，表示最长递增子序列的长度
输入输出样例
样例 1
输入：
8 10 9 2 5 3 7 101 18
输出：
4
样例 2
输入：
6 0 1 0 3 2 3
输出：
4
说明/提示
O(n²) DP 可以过，O(n log n) 更优