SOLUTION\HUGE SOLUTIONSOLUTION
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目描述
给定一个长度为 NNN 的整数序列 a1,a2,…,aNa_1, a_2, \dots, a_Na1 ,a2 ,…,aN ，求该序列中最长严格递增子序列的长度。
子序列是指从原序列中删除若干个元素（也可以不删除）后，剩余元素保持原有相对顺序组成的序列。
严格递增是指子序列中的元素满足 b1<b2<⋯<bkb_1 < b_2 < \dots < b_kb1 <b2 <⋯<bk 。
输入格式
* 第一行包含一个整数 NNN，表示序列的长度。
* 第二行包含 NNN 个整数，表示序列 aaa。
输出格式
* 输出一个整数，表示最长严格递增子序列的长度。
数据范围
* 1≤N≤10001 \le N \le 10001≤N≤1000 (针对 O(N)O(N)O(N) 解法)
* 若 NNN 更大（如 101010），需使用 O(NlogN)O(N \log N)O(NlogN) 解法。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
本题是经典的动态规划问题。我们提供两种解法：动态规划 (O(N)O(N)O(N)) 和 贪心 + 二分查找 (O(NlogN)O(N \log N)O(NlogN))。
方法一：动态规划 (O(N)O(N)O(N))
1. 状态定义
设 dp[i] 表示以第 iii 个元素 a[i]a[i]a[i] 结尾的最长严格递增子序列的长度。
2. 状态转移方程
对于每个位置 iii，我们需要检查它之前的所有位置 jjj (0≤j<i0 \le j < i0≤j<i)：
* 如果 a[j]<a[i]a[j] < a[i]a[j]<a[i]，说明 a[i]a[i]a[i] 可以接在以 a[j]a[j]a[j] 结尾的递增子序列后面，形成一个新的更长的递增子序列。
* 此时，dp[i] 可以更新为 dp[j] + 1。
* 为了得到最长的长度，我们需要取所有满足条件的 jjj 中的最大值。
即：
dp[i]=max0≤j<i,a[j]<a[i](dp[j]+1)dp[i] = \max_{0 \le j < i, a[j] < a[i]} (dp[j] + 1) dp[i]=0≤j<i,a[j]<a[i]max (dp[j]+1)
如果没有任何 jjj 满足 a[j]<a[i]a[j] < a[i]a[j]<a[i]，则 dp[i] 保持初始值 1（即只包含 a[i]a[i]a[i] 自身）。
3. 初始化
* 所有 dp[i] 初始化为 1，因为每个元素本身至少构成一个长度为 1 的子序列。
4. 最终答案
* LIS 不一定以最后一个元素结尾，因此答案是 dp 数组中的最大值，即 max(dp[0],dp[1],…,dp[N−1])\max(dp[0], dp[1], \dots, dp[N-1])max(dp[0],dp[1],…,dp[N−1])。
5. 代码实现 (C++)
6. 复杂度分析
* 时间复杂度：O(N)O(N)O(N)，因为有两层嵌套循环。
* 空间复杂度：O(N)O(N)O(N)，用于存储 a 和 dp 数组。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
方法二：贪心 + 二分查找 (O(NlogN)O(N \log N)O(NlogN))
当 NNN 较大（如 101010 或更大）时，O(N)O(N)O(N) 会超时，需要使用更高效的算法。
1. 核心思想
维护一个数组 tails，其中 tails[k] 存储长度为 k+1k+1k+1 的递增子序列的最小末尾元素。
* 我们希望子序列的末尾元素尽可能小，这样后续才有更多机会接上更大的数，从而形成更长的子序列。
* tails 数组本身是严格递增的。
2. 算法流程
遍历数组中的每个元素 xxx：
3. 如果 xxx 大于 tails 的最后一个元素，说明 xxx 可以延长当前最长的子序列，将 xxx 追加到 tails 末尾。
4. 否则，在 tails 中找到第一个大于或等于 xxx 的元素，并用 xxx 替换它。这一步保证了对于相同长度的子序列，我们保留了更小的末尾元素。
* 这里可以使用 lower_bound 进行二分查找。
5. 最终答案
* tails 数组的长度即为最长递增子序列的长度。
4. 代码实现 (C++)
5. 复杂度分析
* 时间复杂度：O(NlogN)O(N \log N)O(NlogN)，遍历 NNN 个元素，每次二分查找耗时 O(logN)O(\log N)O(logN)。
* 空间复杂度：O(N)O(N)O(N)，最坏情况下 tails 长度为 NNN。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
常见错误与注意事项
1. 非严格递增 vs 严格递增：
* 题目要求严格递增 (<<<)，因此在 DP 中判断条件是 a[j] < a[i]，在二分查找中使用 lower_bound（找第一个 ≥x\ge x≥x 的位置并替换）。
* 如果是非严格递增 (≤\le≤)，DP 条件改为 a[j] <= a[i]，二分查找使用 upper_bound（找第一个 >x> x>x 的位置并替换）。
2. 答案不是 dp[n-1]：
* 很多初学者误以为 LIS 必须以最后一个元素结尾，从而直接输出 dp[n-1]。这是错误的，必须遍历整个 dp 数组找最大值。
3. 初始化问题：
* dp 数组必须初始化为 1，而不是 0。
4. 数据范围：
* 如果 N≤5000N \le 5000N≤5000，O(N)O(N)O(N) 解法通常可以通过。
* 如果 N>5000N > 5000N>5000，建议使用 O(NlogN)O(N \log N)O(NlogN) 解法。
总结
* 小规模数据：使用动态规划，思路清晰，易于实现。
* 大规模数据：使用贪心 + 二分查找，效率高，是面试和竞赛中的标准解法。
根据题目给出的数据范围选择合适的解法即可。
