最长上升子序列c语言
时间: 2024-01-04 09:19:52 浏览: 123
最长上升子序列(Longest Increasing Subsequence,简称LIS)是一个经典的动态规划问题,可以用来求解一个序列中最长的递增子序列的长度。下面是一个用C语言实现最长上升子序列的例子:
```c
#includestdio.h>
int lis(int arr[], int n) {
int dp[n];
int max_len = 1;
(int i = 0; i < n i++) {
dp[i] = 1 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[] = {1, 7, 3, 5, 9, 4, 8};
int n = sizeof(arr) / sizeof(arr[0]);
int result = lis(arr, n);
printf("最长上升子序列的长度为:%d\n", result);
return 0;
}
```
运行结果:
```
最长上升子序列的长度为:4
```
阅读全文