当前位置:   article > 正文

C入门基础题:最长上升子序列(C语言版)

C入门基础题:最长上升子序列(C语言版)

1.题目描述


这是一个简单的动规板子题。
给出一个由 n(n < 5000)个不超过 10“的正整数组成的序列。请输出这个序列的最长上升子序列的长度。
最长上升子序列是指,从原序列中按顺序取出一些数字排在一起,这些数字是逐渐增大的。


2.输入格式


第一行,一个整数 n,表示序列长度。
第二行有 n 个整数,表示这个序列。

3.输出格式

一个整数表示答案。

4.输入输出样例

输入1:
  1. 6
  2. 1 2 4 1 3 4
输入2:
4

5.说明/提示

分别取出 1、2、3、4 即可。

6.代码:

  1. #include <stdio.h>
  2. #define MAX_N 5000
  3. int main() {
  4. int n;
  5. scanf("%d", &n); // 输入序列长度
  6. int arr[MAX_N];
  7. int dp[MAX_N]; // dp[i] 表示以 arr[i] 结尾的最长上升子序列的长度
  8. int max_length = 1; // 最长上升子序列的最大长度
  9. // 输入序列
  10. for (int i = 0; i < n; i++) {
  11. scanf("%d", &arr[i]);
  12. dp[i] = 1; // 初始化每个位置的最长上升子序列长度为 1
  13. }
  14. // 动态规划计算最长上升子序列长度
  15. for (int i = 1; i < n; i++) {
  16. for (int j = 0; j < i; j++) {
  17. if (arr[i] > arr[j]) { // 如果当前元素大于前面的元素
  18. dp[i] = (dp[i] > dp[j] + 1) ? dp[i] : (dp[j] + 1); // 更新 dp[i]
  19. }
  20. }
  21. if (dp[i] > max_length) {
  22. max_length = dp[i]; // 更新最长上升子序列的最大长度
  23. }
  24. }
  25. printf("%d\n", max_length); // 输出结果
  26. return 0;
  27. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/喵喵爱编程/article/detail/939743
推荐阅读
相关标签
  

闽ICP备14008679号