old_Dynamic_Programming/Longest_Increasing_Subsequence.cpp

• View this file on GitHub
• Last update: 2022-07-19 22:14:43+09:00

Code

int longest_increasing_subsequence_length(vector<int> &A){
	int N = A.size();
	vector<int> dp(N, INF);
	for (int i = 0; i < N; i++){
		*lower_bound(dp.begin(), dp.end(), A[i]) = A[i];
	}
	return lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
}

#line 1 "old_Dynamic_Programming/Longest_Increasing_Subsequence.cpp"
int longest_increasing_subsequence_length(vector<int> &A){
	int N = A.size();
	vector<int> dp(N, INF);
	for (int i = 0; i < N; i++){
		*lower_bound(dp.begin(), dp.end(), A[i]) = A[i];
	}
	return lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
}

Back to top page