🧮 最长递增子序列（Longest Increasing Subsequence, LIS）

📝 题目描述

给定一个长度为 n 的整数数组 a[1..n]，请你找出这个数组中最长的严格递增子序列的长度。

一个子序列是从原序列中选出若干个元素组成的序列，要求选出元素的​相对顺序不变​。

严格递增子序列要求满足： 若选择了下标为 i1 < i2 < ... < ik 的若干个数，则满足：

a[i1] < a[i2] < ... < a[ik]

📥 输入格式

• 第一行一个整数 n，表示数组的长度。
• 第二行 n 个整数 a1, a2, ..., an，表示数组中的元素。

📤 输出格式

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

🎯 样例输入 #1

5
10 22 9 33 21

🎯 样例输出 #1

3

解释：最长递增子序列可以是 [10, 22, 33]

🎯 样例输入 #2

8
5 2 8 6 3 6 9 5

🎯 样例输出 #2

4

解释：最长递增子序列可以是 [2, 3, 6, 9]

🚧 边界样例

🧠 解题思路（DP 动态规划）

• 定义状态： 设 dp[i] 表示以第 i 个元素 a[i] 结尾的最长严格递增子序列的长度。
• 初始状态： dp[i] = 1，每个元素本身可以作为一个长度为 1 的子序列。
• 状态转移方程：

  dp[i] = max(dp[i], dp[j] + 1)  其中 j < i 且 a[j] < a[i]
  

• 答案为所有 dp[i] 中的最大值：

  max(dp[1..n])
  

⏱️ 时间复杂度分析

• 时间复杂度：O(n²)
• 空间复杂度：O(n)