leetcode 300. Longest increasing subsequence

300. The longest increasing subsequence

Thought analysis ：
Maintain an array v, In this array v[i] Indicates that the longest subsequence length is i+1 The minimum value of the last bit of the subsequence of , And constantly updated , If the current number num > v[i], be v[i + 1] = num
Boundary situation 1: If the current number is larger than the largest of the array , Then the length should be updated , To add
Boundary situation 2: If the current number is smaller than the smallest of the array , Then the length remains the same , Update minimum

AC Code ：

int lengthOfLIS(vector<int>& nums) {
    
	vector<int> q;
	for(auto x:nums) {
    
	//  Boundary situation 1: If the current number is larger than the largest of the array , Then the length should be updated , To add 
		if(q.empty() || x > q.back())
		q.push_back(x);
		//  Boundary situation 2: If the current number is smaller than the smallest of the array , Then the length remains the same , Update minimum 
		else if(x <= q[0]) q[0] = x;
		else {
    
			//  Binary search update the maintained array 
			int l = 0, r = q.size() - 1;
			while(l < r) {
    
				int mid = (l + r + 1) >> 1;
				if(q[mid] < x) l = mid;
				else r = mid - 1;
			}
			q[r + 1] = x;
		}
	}
	return q.size();
}