首页最长递增子序列c++解法

最长递增子序列c++解法

时间: 2025-01-11 12:50:42 浏览: 40

### C++ 实现最长递增子序列在处理最长递增子序列(Longest Increasing Subsequence, LIS)问题时，可以采用多种方法。一种常见且有效的方法是利用动态规划(Dynamic Programming)[^2]。 #### 动态规划求解LIS 定义 `dp[i]` 表示以第 i 个元素结尾的最长递增子序列的长度，则状态转移方程如下： \[ dp[i] = \max_{j<i,\ nums[j]<nums[i]}(dp[j]+1),\quad 初始条件:\ dp[i]=1 \] 最终的结果即为数组 `dp[]` 中的最大值。这种方法的时间复杂度为 $O(n^2)$，适用于大多数情况下的LIS求解需求[^2]。下面是具体的C++代码实现： ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int lengthOfLIS(vector<int>& nums) { int n = nums.size(); if (!n) return 0; vector<int> dp(n, 1); for(int i=1; i<n; ++i){ for(int j=0; j<i; ++j){ if(nums[j] < nums[i]) dp[i] = max(dp[i], dp[j]+1); } } return *max_element(dp.begin(), dp.end()); } // 测试函数 void test(){ vector<int> nums = {10,9,2,5,3,7,101,18}; cout << "The length of the longest increasing subsequence is: "; cout << lengthOfLIS(nums) << endl; } ``` 上述程序实现了基于动态规划的LIS查找功能，并给出了一组测试数据验证了算法的有效性。对于输入 `[10,9,2,5,3,7,101,18]` ，输出结果应为4，因为存在一个长度为4的严格递增子序列 [2,3,7,101][^5]。

阅读全文