【牛客4456题解析】最长上升子序列的动态规划+二分查找解法
1天前
一、题目解读
牛客4456题要求在一个整数序列中寻找最长上升子序列（LIS）的长度。题目考察的核心是动态规划与高效查找算法的结合，需要设计一种能在给定序列中快速找到最长递增子序列的方法，通常需要平衡时间复杂度和代码简洁性。
二、解题思路
采用动态规划（DP）结合二分查找实现LIS求解。核心思想是：维护一个递增序列dp，每次遍历输入序列A中的元素num，通过lower_bound找到dp中第一个不小于num的位置。若未找到（即num比dp所有元素大），则扩展dp；否则替换该位置元素。由于dp始终递增，其长度即为LIS长度。此优化将时间复杂度从O(N^2)降至O(NlogN)。
三、解题步骤
2. 遍历输入序列：
○ 对每个元素num，使用lower_bound在dp中查找第一个≥num的位置it。
○ 若it为dp末尾（即num比dp所有元素大），则执行dp.push_back(num)，扩展序列。
○ 否则，替换it位置的元素（*it = num），确保dp保持递增且长度最短（因LIS长度相同，但末尾元素更小，后续可容纳更多元素）。
3. 返回结果：dp的长度即为最长上升子序列的长度。
四、代码和注释
class AscentSequence {
public:
int findLongest(vector<int> A, int n) {
vector<int> dp; // 维护一个递增序列
for (int num : A) { // 遍历输入序列
// 使用lower_bound找到第一个不小于当前元素的位置
auto it = lower_bound(dp.begin(), dp.end(), num);
if (it == dp.end()) { // 未找到（num比dp所有元素大）
dp.push_back(num); // 扩展序列
} else { // 找到替换位置
*it = num; // 替换第一个≥num的元素，保持dp递增
}
}
return dp.size(); // 最终序列长度即为LIS长度
}
};五、总结
本解法通过动态规划结合二分查找，将LIS问题的时间复杂度优化至O(NlogN)，显著提升效率。关键在于利用递增序列dp的特性，通过替换操作确保其“紧凑性”，从而在查找时可用lower_bound快速定位。该思路不仅适用于面试算法题，也为处理大规模数据的LIS问题提供了实用策略，是动态规划与高级算法结合的典型案例。
原创内容 转载请注明出处
