DP/LIS.cpp

• View this file on GitHub
• Last update: 2021-03-21 09:59:09+09:00

Verified with

• test/LIS.test.cpp

Code

#pragma once
#include <vector>
#include <algorithm>
#include <limits>

template <class T> int LIS(const std::vector<T>& a) {
	constexpr T INF = std::numeric_limits<T>::max();
	std::vector<T> dp(a.size(), INF);
	for (auto num : a) {
		*std::lower_bound(dp.begin(), dp.end(), num) = num;
	}
	return std::lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
}

#line 2 "DP/LIS.cpp"
#include <vector>
#include <algorithm>
#include <limits>

template <class T> int LIS(const std::vector<T>& a) {
	constexpr T INF = std::numeric_limits<T>::max();
	std::vector<T> dp(a.size(), INF);
	for (auto num : a) {
		*std::lower_bound(dp.begin(), dp.end(), num) = num;
	}
	return std::lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
}

Back to top page