请实现最长递增子序列（LIS）的求解，并说明时间与空间复杂度。

回答思路

1. 能定义状态 dp[i] 表示以第 i 个元素结尾的最长递增子序列长度
2. 能写出 O(n^2) 动态规划转移方程并说明正确性
3. 能给出 O(n log n) 的贪心加二分优化并解释维护数组的含义
4. 能准确分析两种解法的时空复杂度并比较适用场景