c++写一个最长单增子序列算法
时间: 2024-09-26 14:04:00 浏览: 17
在C++中,可以使用动态规划的方法来解决最长递增子序列(Longest Increasing Subsequence, LIS)问题。下面是一个简单的Kadane's Algorithm的实现,它是一种常见的求解最长递增子序列的有效方法:
```cpp
#include <vector>
using namespace std;
int lengthOfLIS(vector<int>& nums) {
if (nums.empty()) return 0;
vector<int> tails(nums.size(), 1); // 初始化tails数组,长度为nums的大小,所有元素初始值为1
int max_len = 1; // 最长递增子序列的长度
for (int i = 1; i < nums.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
tails[i] = max(tails[i], tails[j] + 1);
if (tails[i] > max_len)
max_len = tails[i]; // 更新最长递增子序列长度
}
}
}
return max_len;
}
// 示例
int main() {
vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
cout << "Length of the longest increasing subsequence: " << lengthOfLIS(nums) << endl;
return 0;
}
```
这个算法的时间复杂度是O(n^2),其中n是输入数组的长度。如果你想优化性能,可以考虑使用二分查找或者其他数据结构如斐波那契堆来降低时间复杂度。