【B3637 最长上升子序列】

最长上升子序列

题目描述

这是一个简单的动规板子题。

给出一个由 $n(n\le 5000)$ 个不超过 $10^6$ 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。

最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。

输入格式

第一行，一个整数 $n$，表示序列长度。

第二行有 $n$ 个整数，表示这个序列。

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

6
1 2 4 1 3 4
1
2

样例输出 #1

4
1

提示

分别取出 $1$、$2$、$3$、$4$ 即可。

代码如下：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include 
#include 
#include 

#pragma warning (disable:4996)


using namespace std;

const int x = 5e3;
int dp[x];
int ans[x];

int main() {
    int n;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> ans[i];
	}
    dp[0] = 1;
    for (int i = 1; i < n; i++){
        int maxn = 0;
        //找到前面的数中最长的递增子序列最后一个数，跟当前数比较
        for (int j = 0; j < i; j++){ //遍历前面的数，假设前面的数都是最长递增子序列的最后一个数
            if(ans[j]<ans[i]){ //如果后面的数比前面的数大，它就加入到最长递增子序列中
                maxn = max(dp[j], maxn);//据此找到最长的递增子序列的最后一个数
            }
        }
        //经过循环后，前面的数中最长的递增子序列的最后一个数已经找到且小于当前数
        dp[i] = maxn + 1; //加上自己，最少也是1，就当只有一个数
    }
    sort(dp, dp + n);//找到其中最长的递增子序列
    cout<<dp[n-1]<<endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54