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 5000
 
int 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;
}