请实现最长递增子序列（LIS）长度求解，并使用一个辅助数组 pre 记录每个位置的最优前驱索引。

回答思路

1. 正确给出 O(n^2) 动态规划递推式
2. 说明 pre 数组的存储含义与更新逻辑
3. 能基于 dp 与 pre 回溯构造出具体子序列
4. 正确处理相等元素与初始条件