基于贪心算法和二分搜索编写计算最长上升子序列方法的C语言代码
时间: 2023-06-19 20:09:40 浏览: 98
贪心算法 c语言
以下是基于贪心算法和二分搜索的C语言代码实现:
```c
#include <stdio.h>
//计算最长上升子序列的长度
int LIS(int arr[], int n) {
int len = 1; //当前最长上升子序列的长度
int tail[n]; //tail[i]存储长度为i+1的子序列的最后一个元素的值
tail[0] = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > tail[len-1]) {
tail[len] = arr[i];
len++;
} else {
int l = 0, r = len-1;
while (l < r) {
int mid = (l + r) / 2;
if (tail[mid] < arr[i]) {
l = mid + 1;
} else {
r = mid;
}
}
tail[l] = arr[i];
}
}
return len;
}
int main() {
int arr[] = {10, 9, 2, 5, 3, 7, 101, 18};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Length of LIS is %d\n", LIS(arr, n));
return 0;
}
```
该代码中,我们使用了tail数组来存储长度为i+1的子序列的最后一个元素的值。在遍历数组arr时,我们首先判断arr[i]是否大于tail[len-1],如果是,则将arr[i]加入到tail数组尾部,并将最长上升子序列长度len加1。如果arr[i]小于等于tail[len-1],则使用二分搜索在tail数组中寻找第一个大于等于arr[i]的元素,并将其替换为arr[i]。
在遍历完整个数组后,tail数组中存储的即为最长上升子序列的末尾元素。其长度即为最长上升子序列的长度。
阅读全文