c语言最长递增序列
时间: 2023-07-13 11:23:57 浏览: 57
求解C语言的最长递增子序列可以使用动态规划算法。动态规划算法的基本思想是将原问题分解为若干个子问题,通过求解子问题的最优解来求解原问题的最优解。对于最长递增子序列问题,我们可以定义一个状态数组dp,dp[i]表示以第i个元素为结尾的最长递增子序列的长度。
初始化dp数组的所有元素为1,因为每个元素本身就是一个递增子序列。然后,我们从1到n遍历数组中的每个元素,对于第i个元素,我们从1到i-1遍历之前的所有元素,如果第j个元素小于第i个元素,那么就更新dp[i]的值为dp[j]+1,因为第i个元素可以接在第j个元素的后面形成一个更长的递增子序列。
最终,我们在dp数组中找到最大值,就是整个序列的最长递增子序列的长度。
以下是C语言实现最长递增子序列的代码:
```
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n;
scanf("%d", &n);
int *arr = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
int *dp = (int*)malloc(n * sizeof(int));
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[j] < arr[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
}
}
}
int max_len = 0;
for (int i = 0; i < n; i++) {
if (dp[i] > max_len) {
max_len = dp[i];
}
}
printf("%d\n", max_len);
free(arr);
free(dp);
return 0;
}
```