最长递增子序列c语言
时间: 2023-07-13 17:24:35 浏览: 49
以下是 C 语言实现最长递增子序列的代码:
```c
#include <stdio.h>
int lis(int arr[], int n)
{
int dp[n];
int max = 0;
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
if (dp[i] > max) {
max = dp[i];
}
}
return max;
}
int main()
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Length of LIS is %d", lis(arr, n));
return 0;
}
```
该算法的时间复杂度为 O(n^2),其中 n 是数组的长度。
相关问题
求最长递增子序列c语言
以下是求最长递增子序列的 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 是数组的长度。
c语言最长递增子序列
求解 C 语言的最长递增子序列可以使用动态规划算法,具体步骤如下:
1. 定义一个一维数组 dp,长度为原数组长度,dp[i] 表示以第 i 个元素结尾的最长递增子序列长度。
2. 初始化 dp 数组,将每个元素的最长递增子序列长度初始化为 1。
3. 遍历原数组,对于第 i 个元素,从 0 到 i-1 依次枚举前面的元素 j,若 nums[i] 大于 nums[j],则更新 dp[i],取 dp[j] + 1 和 dp[i] 中的较大值。
4. 遍历 dp 数组,取最大值即为最长递增子序列长度。
以下是 C 语言代码实现:
```c
#include <stdio.h>
int max(int a, int b) {
return a > b ? a : b;
}
int LIS(int nums[], int n) {
int dp[n];
int res = 1;
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
res = max(res, dp[i]);
}
return res;
}
int main() {
int nums[] = {10, 9, 2, 5, 3, 7, 101, 18};
int n = sizeof(nums) / sizeof(nums[0]);
printf("最长递增子序列长度为:%d\n", LIS(nums, n)); // 输出:最长递增子序列长度为:4
return 0;
}
```