最长上升子序列

const int N = 1010;  // 定义数组最大长度
int n;              // 输入的序列长度
int a[N], f[N];     // a数组存储输入序列，f数组存储动态规划状态

int main()
{
    scanf("%d", &n);  // 读入序列长度
    
    // 读入序列中的每个数
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    
    // 动态规划求解最长上升子序列
    for (int i = 1; i <= n; i++)
    {
        f[i] = 1;  // 初始化状态：以a[i]结尾的最长上升子序列至少包含a[i]自身，长度为1
        
        // 遍历i之前的所有位置j，寻找可以接在a[j]后面形成更长上升子序列的情况
        for (int j = 1; j < i; j++)
            if (a[j] < a[i])  // 如果a[j]小于a[i]，则将a[i]接在以a[j]结尾的子序列后面
                f[i] = max(f[i], f[j] + 1);  // 更新f[i]，取当前f[i]和f[j]+1的较大值
    }
    
    // 在所有f[i]中找出最大值，即为最长上升子序列的长度
    int res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, f[i]);
    
    // 输出结果
    printf("%d\n", res);
    
    return 0;
}

• f[i] 表示以第i个元素a[i]结尾的最长上升子序列的长度

• 举例
  假设输入序列为[3, 1, 4, 2, 5]：

  1. 初始化f[1]=1, f[2]=1, f[3]=1, f[4]=1, f[5]=1
  2. 计算过程：
     • f[1] = 1（只有3）
     • f[2] = 1（只有1，因为前面没有比1小的数）
     • f[3] = 2（可以是1,4，因为a[2]=1 < a[3]=4）
     • f[4] = 2（可以是1,2，因为a[2]=1 < a[4]=2）
     • f[5] = 3（可以是1,4,5或1,2,5，取最大值3）
  3. 最终结果：max(f[1…5]) = 3，即最长上升子序列长度为3（例如[1,2,5]）