帮我用c++写一份二分查找求最长不下降子序列长度和数列的代码
时间: 2023-05-24 13:04:49 浏览: 72
以下是用c语言实现二分查找求最长不下降子序列长度和数列的代码:
```
#include <stdio.h>
#include <stdlib.h>
int binary_search(int *nums, int len, int target) {
int l = 0, r = len - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] < target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return l;
}
int longestIncreasingSubsequence(int *nums, int len, int *resArr) {
int *tails = (int*)malloc(len * sizeof(int));
memset(tails, 0, len * sizeof(int));
int lenTails = 1;
tails[0] = nums[0];
resArr[0] = 1;
for (int i = 1; i < len; i++) {
if (nums[i] > tails[lenTails - 1]) {
tails[lenTails++] = nums[i];
resArr[i] = lenTails;
} else {
int index = binary_search(tails, lenTails, nums[i]);
tails[index] = nums[i];
resArr[i] = index + 1;
}
}
free(tails);
return lenTails;
}
int main() {
int nums[] = {1, 3, 5, 7, 9, 2, 4, 6, 8};
int len = sizeof(nums) / sizeof(int);
int *resArr = (int*)malloc(len * sizeof(int));
int LIS_len = longestIncreasingSubsequence(nums, len, resArr);
printf("LIS length: %d\n", LIS_len);
printf("LIS sequence: ");
for (int i = 0; i < len; i++) {
if (resArr[i] == LIS_len) {
printf("%d ", nums[i]);
LIS_len--;
}
}
printf("\n");
free(resArr);
return 0;
}
```
以上程序会输出最长不下降子序列的长度及其子序列。其中,`longestIncreasingSubsequence`函数返回最长不下降子序列的长度,`resArr`存储每个位置的元素在子序列中的位置(方便输出子序列),`binary_search`函数是二分查找实现。