经典dp:最长上升子序列

ChatGPT 可用网址，仅供交流学习使用，如对您有所帮助，请收藏并推荐给需要的朋友。
https://ckai.xyz

1、题目描述

给定一个长度为 N的数列，求数值严格单调递增的子序列的长度最长是多少。输入格式第一行包含整数 N。第二行包含 N 个整数，表示完整序列。输出格式输出一个整数，表示最大长度。

数据范围
1≤N≤10001
−1e9≤数列中的数≤1e9。

输入样例
73 1 2 1 8 5 6

输出样例
4

2、思路剖析

这是一道经典dp问题，我们要求的是最长上升子序列的长度，这个最长的子序列可能是以a[i]结尾的（我们假设数字被存储在数组a中），我们使用一个数组dp[i]来表示以a[i]为结尾的子序列的最大长度，我们最终所求的就是dp数组中的最大值。

如果我们需要求dp[i]，就是以a[i]为结尾的最大值，那么我们就需要知道它的前一个位置是谁，假设它的前一个数字是a[j]，那么dp[i] = dp[j] + 1，也就是以它前一个数字结尾的最大子序列长度再+1。j到底是谁我们不清楚，j的范围是[1, i-1]，我们把最大的（dp[j] + 1）找到，就是最大的dp[i]。

3、代码

#include<iostream>
using namespace std;

const int N = 1e3+10;

int a[N],dp[N];

int main()
{
    int n;
    cin>>n;
    int M = 0;
    for(int i=1;i<=n;++i)cin>>a[i];
    
    for(int i = 1;i<=n;++i)//求dp[i]集合
    {
        dp[i] = 1;//dp[i]最少也有自身的长度
        for(int j=1;j<i;++j)//看看以a[i]结尾的最长子序列的前一个数是哪一个
        {
            if(a[j]<a[i])
            {
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
        //找最长子序列
        M = dp[1];
        for(int i=2;i<=n;++i)
        {
             M = max(M, dp[i]);   
        }
    }
    cout<<M<<endl;
    return 0;
}