C入门基础题：最长上升子序列（C语言版）

1.题目描述

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

2.输入格式

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

3.输出格式

一个整数表示答案。

4.输入输出样例

输入1：

6
1 2 4 1 3 4

输入2：

4

5.说明/提示

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

6.代码：

#include <stdio.h>#define MAX_N 5000int main() {int n;scanf("%d", &n); // 输入序列长度int arr[MAX_N];int dp[MAX_N]; // dp[i] 表示以 arr[i] 结尾的最长上升子序列的长度int max_length = 1; // 最长上升子序列的最大长度// 输入序列for (int i = 0; i < n; i++) {scanf("%d", &arr[i]);dp[i] = 1; // 初始化每个位置的最长上升子序列长度为 1}// 动态规划计算最长上升子序列长度for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (arr[i] > arr[j]) { // 如果当前元素大于前面的元素dp[i] = (dp[i] > dp[j] + 1) ? dp[i] : (dp[j] + 1); // 更新 dp[i]}}if (dp[i] > max_length) {max_length = dp[i]; // 更新最长上升子序列的最大长度}}printf("%d\n", max_length); // 输出结果return 0;
}