前情提要：蓝桥杯校赛压轴题，是道朴素最长上升子序列板子题；没做出来，故学习记录一下

题目链接

设原数列为 1,2,4,1,3,4，$f(x)$ 表示以第 $i$ 个数为结尾的最长上升子序列的长度

n 1 2 3 4 5 6
$a_i$ 1 2 4 1 3 4
$f(n)$ 1 2 3 1 3 4

代码实现

  • 读入数据
  • 大循环开始，从 $1$ 到 $n$，计算 $f_i$，记得初始值是 $1$
  • 小循环，从 $1$ 到 $i−1$，如果 $a_j$ 小于 $a_i$ 的话，说明这个数可以和 $f_i$ 组成上升子序列，则 $f_i$ 取 $max⁡(f_i,f_j+1)$
  • 寻找最大值

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;

const int N = 5e3;
int a[N+10];
int f[N+10];

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

二分优化

我们定义一个数组 tails，其中 tails[k] 表示长度为 $k+1$ 的上升子序列的最小尾元素。该数组帮助我们追踪可能构成的上升子序列的最小值，从而达到优化的效果。算法的核心步骤是：

  1. 遍历数组 a 中的每个元素 num。

  2. 使用二分查找在 tails 中找到第一个大于等于 num 的位置 pos。

    • 如果 pos 等于 tails 的长度，说明 num 比 tails 中所有元素都大，可以直接将 num 添加到 tails 末尾，增加子序列长度。

    • 否则，用 num 替换 tails[pos]，以确保 tails 保持递增且末尾值尽可能小。

  3. 最终 tails 的长度即为最长上升子序列的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 5e3;
int a[N+10];

signed main(){
    int n;cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    vector< int > tails;
    for(int i = 1;i <= n;i ++){
        int num = a[i];
        auto pos = lower_bound( tails.begin() , tails.end() , num );
        if( pos == tails.end() ){
            tails.push_back( num );// 如果 num 比所有元素都大，添加到末尾
        }else{
            *pos = num;// 替换找到的第一个 >= num 的位置，保证尾部元素尽量小
        }
    }
    cout << tails.size() << endl;
    return 0;
}