$\Huge\color{orchid}{点击此处获取更多干货}$

动态规划

问题中“子序列”指的是从原序列中取出任意一部分元素，并保持其原来的顺序构成的序列，这些元素在原来的序列中不一定要全部连续。比如说序列$\{49,28,77,35,14\}$，从中取出第$1,2,4$个元素按顺序构成$\{49,28,35\}$，就是该序列的子序列。如果这个子序列中的元素从头端到尾端单调增加，那么就称它为“上升子序列”，现在需要求解的就是这些上升子序列中最长的长度。

我们可以将问题分解成更细微的部分，首先对于序列中的每一个单独元素，我们都把它当成长度为1的上升子序列。然后对于序列$s$上某个位置的元素$s[i]$，如果在$1\sim i-1$的区间上有一个元素$s[j]$满足$s[j]<s[i]$，那么$\{s[j],s[i]\}$就可以构成长度为2的上升子序列。如果位置$j$还是某条长度为$L$的上升子序列的末尾，那么追加上$s[i]$后就可以构成以$i$为末尾的上升子序列。该子序列是否最长，都满足这个性质。

接下来，我们用$dp(i)$表示以$i$结尾的上升子序列的最大长度，可以根据上面的性质得出，当$j<i$时，有下面的递推式：
$$dp(i)=\begin{cases}max\{dp(i),dp(j)+1\},s[i]>s[j] \\dp(i),s[i]\le s[j]\end{cases}$$
$s[i]\le s[j]$时，无法用$j$去更新$i$，$dp(i)$保持不变，$s[i]>s[j]$时，再取一个$k<j,s[k]<s[j]$，假设$dp(j)=x,dp(k)>(x+1)$，那么在遇上$j$位置之前，$dp(i)$就已经通过$dp(k)$更新完毕了，而不会再有$dp(j)$什么事。所以如果此时保证了$j$位置上的是最优解，那么$i$位置上也就是最优解了。

由上面的递推公式可得出，整个序列的最长上升子序列一定会以序列中某个位置$i$结束，这样的话其长度就是以每个位置为结尾的最长上升子序列长度之间的最大值。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int* arr = new int[n], 
        * dp = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        dp[i] = 1;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {              //(j,i)能构成上升子序列，就按照递推公式去推
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    cout << *max_element(dp, dp + n) << endl;   //输出所有位置为末尾的情况下，最长上升子序列长度的最大值
    return 0;
}