printsdf's blog
0%

最长上升子序列题解

发表于 更新于 分类于 ，
本文字数： 1.1k 阅读时长 ≈ 1 分钟

1. base

这是一个线性dp的版本，它的数据范围在1000

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

输入格式

第一行包含整数 $N$。

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

输出格式

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

数据范围

$1≤N≤1000$，
$−10^9≤数列中的数≤10^9$

输入样例：

1
2
7
3 1 2 1 8 5 6

输出样例：

1
4

DP分析

23558fd23229a69e3a50d02b8e8ac61

代码

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n;
int w[N], f[N];

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

2. 进阶

数据范围更大，使用DP会TLE(Time Limit Error)

数据范围

$1≤N≤1000000$，
$−10^9≤数列中的数≤10^9$​

分析

存储每个长度中最后的数最小的情况，必定这个数组是单调递增的，可以用二分。

代码

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

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

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )  cin >> a[i];
   
    int len = 0;
    q[0] = -2e9;
    for (int i = 0; i < n; i ++ )
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i])  l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }
    
    cout << len << endl;
    return 0;
}