题目描述
给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N≤1000,
−10^9≤数列中的数≤10^9
输入样例:
7
3 1 2 1 8 5 6
输出样例:(1 2 5 6)
4
算法1
(DP) $O(n^2)$
参考题解:y总视频
C++ 代码
//y总题解
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N],a[N];
int n;
int main(){
scanf("%d",&n);
for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
for (int i = 1;i <= n;i++){
f[i] = 1;//边界初始条件,假设倒数第二个数不存在
for (int j = 1;j < i;j++){
if (a[j] < a[i]){
f[i] = max(f[i],f[j]+1);
}
}
}
int res = 0;
for (int i = 1;i <= n;i++) res = max(res,f[i]);
printf("%d",res);
return 0;
}
算法2
(DP+二分) $O(n*logn)$
参考题解:https://www.acwing.com/solution/content/4807/
-
状态表示:f[i]表示长度为i的最长上升子序列,末尾最小的数字。(长度为i的最长上升子序列所有结尾中,结尾最小min的) 即长度为i的子序列末尾最小元素是什么。
-
状态计算:对于每一个w[i], 如果大于
f[cnt-1]
(下标从0开始,cnt长度的最长上升子序列,末尾最小的数字),那就cnt+1,使得最长上升序列长度+1,当前末尾最小元素为w[i]。 若w[i]小于等于f[cnt-1],说明不会更新当前的长度,但之前末尾的最小元素要发生变化,找到第一个大于或等于 (这里不能是大于) w[i],更新以那时候末尾的最小元素。 -
f[i]一定是一个单调递增的数组,所以可以用二分法来找第一个大于或等于w[i]的数字。(可以用STL)
写法1
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N],w[N];
int n,cnt;
int main(){
cin >> n;
for (int i = 1;i <= n;i++) cin >> w[i];
f[cnt++] = w[1];
for (int i = 2;i <= n;i++){
if (w[i] > f[cnt-1]) f[cnt++] = w[i];
else{
//注意二分的左边界一定要是f[0]
int l = 0,r = cnt-1;
while (l < r){
int mid = l+r >> 1;
if (w[i] <= f[mid]) r = mid;
else l = mid + 1;
}
f[r] = w[i];
}
}
cout << cnt << endl;
return 0;
}
写法2 STL
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N],w[N];
int n,cnt;
int main(){
cin >> n;
for (int i = 1;i <= n;i++) cin >> w[i];
f[cnt++] = w[1];
for (int i = 2;i <= n;i++){
if (w[i] > f[cnt-1]) f[cnt++] = w[i];
else{
int r = lower_bound(f,f+cnt-1,w[i])-f;
f[r] = w[i];
}
}
cout << cnt << endl;
return 0;
}