求最长递增子序列c语言
时间: 2023-07-13 17:26:55 浏览: 111
求最长子序列 c语言编写
5星 · 资源好评率100%
以下是求最长递增子序列的 C 语言实现代码:
```c
#include <stdio.h>
int lis(int arr[], int n) {
int dp[n], max_len = 1;
// 初始化 dp 数组
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
// 计算最长递增子序列的长度
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
}
}
if (dp[i] > max_len) {
max_len = dp[i];
}
}
return max_len;
}
int main() {
int arr[] = {10, 22, 9, 33, 21, 50, 41, 60};
int n = sizeof(arr) / sizeof(arr[0]);
printf("最长递增子序列的长度为:%d\n", lis(arr, n));
return 0;
}
```
该算法的时间复杂度为 O(n^2),其中 n 是数组的长度。
阅读全文