二分优化 O(n logn)

思路

为了让子序列更长，让每一个长度的最长上升子序列的末尾元素尽可能小，这样后面元素能接到这个子序列的可能就更大。

所以，创建一个 dp 向量，用来存储各个长度的子序列末尾的最小元素。

那么考虑 arr 数组下的每一个元素 x ，遍历 dp 向量，如找到 x < dp[i] ，停止遍历：

1. x < dp[i] ：找到了第一个末尾元素大于 x 的子序列长度 i ，前面所有的子序列长度最小末尾元素均小于 x ，所以当前 x可以放在长度为 i-1 的子序列末尾，此时新形成的子序列长度为 i ，末尾元素又小于 dp[i] ，因此这个元素应当取代 dp[i] ；
2. x >= dp[i] ：继续遍历，x 无法加入此前任何一个子序列使得它的末尾元素更小。（如果 dp 数组已经遍历完了，就代表 x 只能放在长度为 dp.size() 的子序列末尾构成长度为 dp.size()+1 的子序列，所以 dp.push_back(x) ）

当 arr 数组遍历完成，dp.size() 即为所求。

当然，因为遍历规则，dp 向量的元素呈非严格递减排列，因此可以使用二分查找优化遍历 dp 向量的过程。

代码

#include<bits/stdc++.h>
using namespace std;

int n,a[100100];
vector<int> dp;

int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	for(int i=1;i<=n;i++){
		auto it=lower_bound(dp.begin(),dp.end(),a[i]);
		
		if(it==dp.end()) dp.push_back(a[i]);
		else *it=a[i];
	}
	
	cout<<dp.size();
	
	return 0;
}

声明：个人学习经验，如有谬误，欢迎指出。