首页c++ 最长上升子序列LIS

c++ 最长上升子序列LIS

时间: 2025-02-24 15:33:36 浏览: 80

### C++ 实现最长上升子序列 (LIS) 算法 #### 示例代码解释对于给定的一个整数数组 `a`，目标是找出其中最长的严格递增子序列并返回该序列的最大长度。下面展示了一种基于动态规划的方法来解决问题。 ```cpp #include <iostream> #include <algorithm> // For std::max function using namespace std; int main() { int a[1005], dp[1005], ans = 0; int n; cin >> n; // 输入数组大小 for (int i = 1; i <= n; ++i) { cin >> a[i]; // 输入数组元素 } for (int i = 1; i <= n; ++i) { dp[i] = 1; // 初始化dp数组，默认每个位置至少可以构成长度为1的上升子序列 for (int j = 1; j < i; ++j) { if (a[j] < a[i]) { // 如果存在更早的位置上的数值小于当前位置，则更新dp值 dp[i] = max(dp[i], dp[j] + 1); } } ans = max(ans, dp[i]); // 更新最大上升子序列长度 } cout << ans; // 输出最终的结果 return 0; } ``` 这段程序首先读取输入的数据到数组 `a[]` 中，并初始化另一个同样大小的辅助数组 `dp[]` 来记录到达每一个索引处所能形成的最长上升子序列的长度。遍历整个数组，在每一步都尝试寻找之前已经访问过的所有可能形成新的上升子序列的情况，并据此调整当前节点对应的 `dp[]` 值。最后输出的是在整个过程中发现的最大上升子序列长度[^1]。此方法的时间复杂度为 O(n²)，适用于较小规模的数据集（n ≤ 1e4）。当面对更大范围内的数据时，建议采用更加高效的算法比如贪心加二分查找的方式来进行优化处理[^5]。

阅读全文