You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
5.6 KiB
5.6 KiB
一、题目描述
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长 是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数，表示完整序列。
输出格式 输出一个整数，表示最大长度。
数据范围
1≤N≤100000，
−10^9≤数列中的数≤10^9
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4
二、贪心+二分优化
1、朴素算法
状态表示：
- 集合:
f[i]表示以a[i]结尾 的最长的上升序列长度- 属性：
max
前一版本：N≤1000，本题要求：N≤100000
N的数据范围大了100倍,前一版本动态规划代码的时间复杂度是O(N^2),1000^2=1000000，是1e6，是可以1秒过的，但如果是100000^2=10000000000,是1e10，超时，需要优化~
2、贪心+二分算法
思想 : 对于同样长度的子串，希望它的末端越小越好，这样后面更易扩展它,使数列更长。
状态表示：
- 集合：
f[i]表示长度为i的递增子序列中，末尾元素最小的是f[i]- 属性：这个挺特殊，不是
max,min,而是最终数列的长度fl
算法步骤
f[fl]:f中的最后一个数字,fl是数组中的游标。
扫描每个原序列中的数字a[i]:
① 如果a[i]大于f[fl],f[++fl]=a[i],把a[i] 接 在f[]数组的最后面
② 如果a[i]小于f[fl],在f中查找并替换第一个大于等于它元素
解释：这样操作就可以使得长度一样的上升子序列的每个位置是最小的数字！
举栗子
a |
3 |
1 |
2 |
1 |
8 |
5 |
6 |
|---|
开始时f[]为空，数字3进入序列
a |
3 |
1 |
2 |
1 |
8 |
5 |
6 |
|---|
f |
3 |
|---|
1 比 3 小, 3出序列 ，1入序列
a |
3 |
1 |
2 |
1 |
8 |
5 |
6 |
|---|
f |
1 |
|---|
2 比 1 大,2入序列
a |
3 |
1 |
2 |
1 |
8 |
5 |
6 |
|---|
f |
1 |
2 |
|---|
1 比 2 小,在f中找到第一个大于等于1的位置，并替换掉原来的数字
a |
3 |
1 |
2 |
1 |
8 |
5 |
6 |
|---|
f |
1 |
2 |
|---|
8 比 2 大
a |
3 |
1 |
2 |
1 |
8 |
5 |
6 |
|---|
f |
1 |
2 |
8 |
|---|
5 比 8 小,在f中找到第一个大于等于5的数字，并替换掉原来的数字
a |
3 |
1 |
2 |
1 |
8 |
5 |
6 |
|---|
f |
1 |
2 |
5 |
|---|
6 比 5 大
a |
3 |
1 |
2 |
1 |
8 |
5 |
6 |
|---|
f |
1 |
2 |
5 |
6 |
|---|
f 的长度fl就是最长递增子序列的长度
3、时间复杂度
\large O(N*logN)四、实现代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, a[N];
// 数组模拟
int f[N], fl;
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
// 1、首个元素
f[0] = a[0];
// 2、后续元素开始计算
for (int i = 1; i < n; i++) {
if (a[i] > f[fl])
f[++fl] = a[i];
else
// 利用STL的二分，在f中查找第一个大于等于a[i]的值，并完成替换
*lower_bound(f, f + fl, a[i]) = a[i];
}
// 栈内元素数量就是答案
printf("%d\n", fl + 1);
return 0;
}