最长序列子序列,c语言
时间: 2024-09-20 14:05:35 浏览: 25
最长递增子序列(Longest Increasing Subsequence,LIS)是一个经典的计算机科学问题,通常用动态规划方法解决。在C语言中,可以编写一个函数来找到一个数组中最长的递增子序列长度。以下是基本的算法思路:
```c
#include <stdio.h>
#include <stdlib.h>
// 动态规划函数,lis[i]表示以nums[i]结尾的最长递增子序列长度
int lis(int nums[], int n) {
int *dp = (int*)malloc(n * sizeof(int)); // 初始化dp数组,所有元素为1
dp[0] = 1;
for (int i = 1; i < n; i++) {
// 遍历数组,比较当前元素与前面元素
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1); // 更新dp[i]
}
}
}
// 找到最长递增子序列的长度
int result = *max_element(dp, dp+n);
free(dp); // 释放内存
return result;
}
int main() {
int arr[] = {10, 9, 2, 5, 3, 7, 101, 18};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Length of Longest Increasing Subsequence: %d\n", lis(arr, n));
return 0;
}
```
上述代码首先创建一个动态规划数组 `dp`,每个元素表示到当前位置为止的最大递增子序列长度。然后遍历数组,对于每个元素,如果它大于某个已经处理过的元素,则更新其对应的 `dp` 值。最后返回整个数组的最大 `dp` 值即为最长递增子序列的长度。