给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式
第一行包含整数 N。

第二行包含 N 个整数，表示完整序列。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N≤1000，
−10 ^ 9≤数列中的数≤10 ^ 9

输入样例：
7
3 1 2 1 8 5 6

输出样例：
4

最长上升子序列–LIS问题

题意：给我们一条长度为n的数列，从中找到一个长度严格递增的子序列（可以有间隔），并且是最长的那一个，输出长度的最大值。

Sample：3 1 2 1 8 5 6中最长上升子序列是1 2 5 6，输出4。

LIS是一道经典的线性dp问题。

由于题中的数列是一个一维的序列，因此我们可以用一个一维的数组dp，来进行状态表示和计算。

一、dp[i]的状态表示：

（从集合的角度分析dp问题，这很重要，因为dp能够优化问题的核心在于：它能表示一个集合，一类一类地进行表示，大大提高了解决问题的效率。）

①集合：所有以a[i]结尾的严格单调上升子序列。

②属性：Max（一般还有：Count，Min）

综合一下：dp[i]表示所有以a[i]结尾的严格单调上升子序列长度的Max值。

二、dp[i]的状态计算（核心：集合划分）

dp[i]表示了很多上升子序列的集合，我们用一个椭圆来表示所有以a[i]结尾的严格单调上升子序列。

①目标：求取dp[i]的值（所有以a[i]结尾的严格单调上升子序列长度的Max值）

dp[i]不太好直接求，dp中有个很重要的思想是“分而治之”，我们将所有这样形式的单调上升子序列分为若干比较好算的类，最终dp[i]就是每一类的最大值取Max。

②集合划分依据：以最后一个不同的元素，即倒数第二个元素，可能的情况有i类（不妨设下标从1开始）：a[1]，a[2]，...，a[i-1]，不存在。

• (1)如果倒数第二个数不存在，那么其值就是1，序列之中只有a[i]一个元素。

• (2)如果倒数第二个数是a[k](k=1,2,3，...，i-1),所有倒数第二个元素是a[k]的序列都可以分为两部分：

• • 第一部分：a[i]（最后一个元素）
• • 第二部分：除了a[i]的剩余部分（最后一个元素是a[k]）

如果求其中的最大值，即Max(第二部分)+1（第一部分），我们从定义出发可以直接得出结果，也就是状态转移方程：dp[k] + 1。

椭圆如图所示：

还有个要注意的点，我们划分的某一类可能会不存在，如果a[k]>=a[i]则意味着我们当前分的这一类所有序列都是不合法的，无需考虑，因此我们在划分集合的时候要特殊判断一下该类是否存在（a[k]<a[i]才存在）

分析完dp[i]的状态表示之后，所有的状态全部求完，那么答案就是：max(dp[1],dp[2],...,dp[n])

（最长上升子序列一定是以某个数结尾的，则考虑以所有数结尾的情况，再取max，这样取得的max一定是包含了所有的情况）

时间复杂度

O(n2)：状态数(n) * 转移数(n)

代码：

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int a[N],dp[N];
int n;

int main()
{
    cin>>n;
    
    for(int i=1;i<=n;i++) cin>>a[i];
    
    for(int i=1;i<=n;i++)
    {
        dp[i]=1;
        for(int j=1;j<i;j++)
            if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1);
    }
    
    int res=0;
    for(int i=1;i<=n;i++)
        res=max(res,dp[i]);
    cout<<res<<endl;
    
    return 0;
}