mmrz's library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

LIS
(z_other/longest_increasing_subsequences.hpp)

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Include: #include "z_other/longest_increasing_subsequences.hpp"

LIS

使い方

longest_increasing_subsequences<bool is_strict, T>(vector<T> v) : $v$ の最長増加部分列の長さを返す。

• is_strict = true の時、狭義単調増加
• is_strict = false の時、講義単調増加

Verified with

• verify/aoj/dpl/1_D.test.cpp

Code

#pragma once

#include<algorithm>
#include<vector>

template <bool is_strict, class T>
int longest_increasing_subsequences(const std::vector<T>& v){
	std::vector<T> dp;

	auto it = dp.begin();

	for(auto elem : v){
		if constexpr (is_strict){
			it = std::lower_bound(dp.begin(), dp.end(), elem);
		}else{
			it = std::upper_bound(dp.begin(), dp.end(), elem);
		}
		if(it == dp.end()){
			dp.push_back(elem);
		}else{
			*it = elem;
		}
	}

	return int(dp.size());
}

#line 2 "z_other/longest_increasing_subsequences.hpp"

#include<algorithm>
#include<vector>

template <bool is_strict, class T>
int longest_increasing_subsequences(const std::vector<T>& v){
	std::vector<T> dp;

	auto it = dp.begin();

	for(auto elem : v){
		if constexpr (is_strict){
			it = std::lower_bound(dp.begin(), dp.end(), elem);
		}else{
			it = std::upper_bound(dp.begin(), dp.end(), elem);
		}
		if(it == dp.end()){
			dp.push_back(elem);
		}else{
			*it = elem;
		}
	}

	return int(dp.size());
}

Back to top page