C++最长上升子序列并输出
时间: 2024-05-14 12:14:21 浏览: 100
最长上升子序列
以下是C语言实现最长上升子序列的代码,并输出该子序列:
```c
#include <stdio.h>
int main() {
int n, i, j, max_len = 1, max_index = 0;
int a[1000], dp[1000], pre[1000];
printf("请输入序列长度:");
scanf("%d", &n);
printf("请输入序列:");
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
dp[i] = 1;
pre[i] = -1;
for (j = 0; j < i; j++) {
if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
pre[i] = j;
}
}
if (dp[i] > max_len) {
max_len = dp[i];
max_index = i;
}
}
printf("最长上升子序列长度为:%d\n", max_len);
printf("最长上升子序列为:");
while (max_index != -1) {
printf("%d ", a[max_index]);
max_index = pre[max_index];
}
printf("\n");
return 0;
}
```
在该代码中,我们使用动态规划的思想解决了最长上升子序列问题。首先,我们定义一个数组dp,表示以a[i]结尾的最长上升子序列长度。对于dp[i],我们需要遍历j(0<=j<i),当a[j]<a[i]时,dp[i]的值应该为dp[j]+1。同时,我们需要记录一个pre数组,表示a[i]前面的最长上升子序列中,a[i]的前一个元素是哪个。最后,我们找到dp数组中最大的值max_len,以及对应的下标max_index,用pre数组回溯得到最长上升子序列。
阅读全文