A27146. 下面 LIS 函数试图求出最长上升子序列的长度，其时间复杂度为（ ）。#define INT_MIN(-1000) int LIS(vector<int>& nums){ int n= nums.size(); vector<int>tail; tail.push back(INT_MIN); for(inti=0;i<n; i++){ int x=nums[i],l=0,r= tail.siz…

下面 LIS 函数试图求出最长上升子序列的长度，其时间复杂度为（    ）。

#define INT_MIN(-1000)
int LIS(vector<int>& nums){
	int n= nums.size();
	vector<int>tail;
	tail.push back(INT_MIN);
	for(inti=0;i<n; i++){
		int x=nums[i],l=0,r= tail.size();
		while(l<r){
			int mid =(l+r)/ 2;
			if(tail[mid]< x)
				l= mid + 1;
			else
				r= mid;
		}
		if(r == tail.size())
			tail.push_back(x);
		else
			tail[r]= x;
	}
	return tail.size()-1;
}