用C语言写出来 在“最长递增子序列”的基础上对代码进行改进,输出一条最长递增子序列。 输入 每组输入包括两行,第一行为序列长度n,第二行为序列。 输出 输出最长递增子序列中的任意一条即可。 样例输入 Copy 7 1 7 3 4 9 2 3 样例输出 Copy 1 3 4 9
时间: 2023-06-20 14:03:32 浏览: 80
首先,我们需要先求出最长递增子序列的长度,然后再根据动态规划求解的思路,回溯得到最长递增子序列。
以下是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 1000
int dp[MAX_N]; // 存储最长递增子序列的长度
int pre[MAX_N]; // 存储每个元素在最长递增子序列中的前驱
int LIS(int *seq, int n) {
int max_len = 0; // 最长递增子序列的长度
int end = 0; // 最长递增子序列的末尾元素下标
for (int i = 0; i < n; i++) {
dp[i] = 1;
pre[i] = -1;
for (int j = 0; j < i; j++) {
if (seq[j] < seq[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
pre[i] = j;
}
}
if (dp[i] > max_len) {
max_len = dp[i];
end = i;
}
}
// 回溯得到最长递增子序列
int lis[MAX_N], len = 0;
while (end != -1) {
lis[len++] = seq[end];
end = pre[end];
}
// 输出最长递增子序列
for (int i = len - 1; i >= 0; i--) {
printf("%d ", lis[i]);
}
printf("\n");
return max_len;
}
int main() {
int n, seq[MAX_N];
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &seq[i]);
}
int len = LIS(seq, n);
printf("Length of LIS: %d\n", len);
return 0;
}
```
输入样例:
```
7
1 7 3 4 9 2 3
```
输出样例:
```
1 3 4 9
Length of LIS: 4
```
阅读全文