最长递增子序列 动态规划 c
时间: 2023-10-13 19:18:31 浏览: 52
最长递增子序列是一个经典的动态规划问题,在程序设计竞赛、算法竞赛等领域被广泛应用。下面是一个用C语言实现的最长递增子序列算法。
算法思路:
我们可以用dp[i]表示以第i个数结尾的最长递增子序列的长度,那么状态转移方程为:
dp[i] = max{dp[j] + 1 | j < i && a[j] < a[i]}
即枚举i前面的所有位置j,如果a[j] < a[i],则可以将i加入以j结尾的最长递增子序列,长度加1,取所有可能的情况中的最大值。
最终的结果为dp数组中的最大值。
代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000
int a[MAXN], dp[MAXN];
int max(int x, int y) {
return x > y ? x : y;
}
int main() {
int n, ans = 1;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
dp[i] = 1;
for (int j = 1; j < i; j++) {
if (a[j] < a[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
}
printf("%d\n", ans);
return 0;
}
```
输入格式:第一行为序列长度n,接下来一行为n个整数,表示序列。
输出格式:一行,表示最长递增子序列的长度。
例如,输入:
```
5
1 5 2 3 4
```
输出:
```
4
```