解题思路

使用动态规划算法。

设 $dp[i]$ 表示以 $nums[i]$ 结尾的最长严格递增子序列长度。

对于每个位置 $i$，枚举它前面的所有位置 $j$：

如果 $nums[j] < nums[i]$，说明 $nums[i]$ 可以接在 $nums[j]$ 后面，此时可以更新：

题目描述

给定一个长度为 $n$ 的整数数组 $nums$，请你找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，可以删除（或不删除）数组中的元素，但不能改变其余元素的相对顺序。

例如，$[3,6,2,7]$ 是数组 $[0,3,1,6,2,2,7]$ 的子序列。

输入描述

第一行输入一个整数 $n$，表示数组 $nums$ 的长度。

第二行输入 $n$ 个整数，表示数组 $nums$ 中的元素。

输出描述

输出一个整数，表示数组 $nums$ 中最长严格递增子序列的长度。

样例 $1$

输入：

8
10 9 2 5 3 7 101 18

输出：

4

解释：

最长递增子序列是 $[2,3,7,101]$，因此长度为 $4$。

样例 $2$

输入：

6
0 1 0 3 2 3

输出：

4

样例 $3$

输入：

7
7 7 7 7 7 7 7

输出：

1

提示

• $1 \le n \le 2500$
• $-10^4 \le nums_i \le 10^4$