最长不下降子序列

问题描述：

统计一个数组中的最长不下降子序列。

示例：

输入：14

输入：13 7 9 16 38 24 37 18 44 19 21 22 63 15

输出：8（其中是7 9 16 18 19 21 22 63）

方法：借鉴B站UP主T_zhao的讲解视频，感谢。附上视频链接：详细分析如何求具体的最长不下降子序列 奥赛一本通 1259：【例9.3】求最长不下降序列_哔哩哔哩_bilibili

如有侵权，会主动删帖。

代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<math.h>
int max(int a, int b) {return a > b ? a : b;
}int main() {int a[50], n,maxnum = 0 , i, j;int dp[50];printf("please input n:\n");scanf("%d", &n);printf("please input num:\n");for (i = 0; i < n; i++) {scanf("%d", &a[i]);dp[i] = 1;//初始化dp}for(i=0;i<n;i++){//从第一个数开始往前遍历找比它小的数，更新dpfor (j = 0; j < i; j++) {if (a[i] >= a[j]) {dp[i] = max(dp[i], dp[j] + 1);//与每一个比当前数小的dp+1作比较，存储最大的}}}for (i = 0; i < n; i++) {if (maxnum < dp[i]) {maxnum = dp[i];}}printf("the longest not decline child sequence num is: %d\n", maxnum);return 0;
}

如果想输出最长不下降子序列，则可以像B站UP主所说的那样，多用一个pre数组存储路径。

运行结果截图：

如果该内容对你有小小的帮助，请给我点个赞！谢谢。