longest_increasing_subsequence

関数 · 文字列ユーティリティ

template <class T>
int longest_increasing_subsequence(const std::vector<T> &v, bool strict = true);

概要

最長増加部分列の長さ

計算量

• $O(n\log n)$

関連項目

• longest_common_prefix — 最長共通接頭辞 (longest common prefix)
• longest_common_suffix — 最長共通接尾辞 (longest common suffix)
• minimum_period — s を隙間なく敷き詰める最小の周期を求める（s の長さを割り切る最小の $i$）
• is_palindrome — 回文判定
• is_palindromic_number — 回文数判定
• is_correct_parenthesis_sequences — 正しい括弧列か判定
• run_length_encoding — ランレングス圧縮
• make_lis — 最長増加部分列を構成する添字列
• split — 文字列を区切り文字で分割する
• join — 文字列を区切り文字で連結する
• next_string — 辞書順で次の順列（文字列版、std::next_permutation のラッパ）
• to_lower — 全文字を小文字に変換した文字列を返す
• to_upper — 全文字を大文字に変換した文字列を返す