Longest Increasing Subsequence - 最長増加部分列
(Library/Other/LongestIncreasingSubsequence.hpp)

• View this file on GitHub
• Last update: 2025-04-30 01:32:17+09:00
• Include: #include "Library/Other/LongestIncreasingSubsequence.hpp"

Depends on

• Library/Common.hpp

Verified with

• verify/LC-LongestIncreasingSubsequence.test.cpp

Code

/**
 * @file LongestIncreasingSubsequence.hpp
 * @brief Longest Increasing Subsequence - 最長増加部分列
 * @author ei1333 (Original)
 * @version 2.0
 * @date 2024-10-29
 */

#include "../Common.hpp"

/**
 * @brief 配列 `data` の最長増加部分列を求める。
 * @tparam Strict 狭義単調増加であるか
 * @param data 求める配列
 * @return vector<T> 最長増加部分列の 1 つで、各要素を `data` における添え字で表した配列
 * @note 返り値の配列の長さが最長増加部分列の長さである。
 */
template<bool Strict, typename T>
vector<T> LongestIncreasingSubsequence(const vector<T> &data){
    int N = (int)data.size();
    T inf = numeric_limits<T>::min();
    vector<T> L, pre, S;
    for(auto &x : data){
        typename vector<T>::iterator itr;
        if(Strict) itr = lower_bound(L.begin(), L.end(), x);
        else itr = upper_bound(L.begin(), L.end(), x);
        if(itr == L.begin()) pre.emplace_back(inf);
        else pre.emplace_back(*prev(itr));
        if(itr == L.end()) L.emplace_back(x);
        else *itr = x;
    }
    T x = L.back();
    for(int i = N - 1; x != inf;){
        while(data[i] != x) --i;
        S.emplace_back(i);
        x = pre[i];
    }
    reverse(S.begin(), S.end());
    return S;
}

#line 1 "Library/Other/LongestIncreasingSubsequence.hpp"
/**
 * @file LongestIncreasingSubsequence.hpp
 * @brief Longest Increasing Subsequence - 最長増加部分列
 * @author ei1333 (Original)
 * @version 2.0
 * @date 2024-10-29
 */

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 10 "Library/Other/LongestIncreasingSubsequence.hpp"

/**
 * @brief 配列 `data` の最長増加部分列を求める。
 * @tparam Strict 狭義単調増加であるか
 * @param data 求める配列
 * @return vector<T> 最長増加部分列の 1 つで、各要素を `data` における添え字で表した配列
 * @note 返り値の配列の長さが最長増加部分列の長さである。
 */
template<bool Strict, typename T>
vector<T> LongestIncreasingSubsequence(const vector<T> &data){
    int N = (int)data.size();
    T inf = numeric_limits<T>::min();
    vector<T> L, pre, S;
    for(auto &x : data){
        typename vector<T>::iterator itr;
        if(Strict) itr = lower_bound(L.begin(), L.end(), x);
        else itr = upper_bound(L.begin(), L.end(), x);
        if(itr == L.begin()) pre.emplace_back(inf);
        else pre.emplace_back(*prev(itr));
        if(itr == L.end()) L.emplace_back(x);
        else *itr = x;
    }
    T x = L.back();
    for(int i = N - 1; x != inf;){
        while(data[i] != x) --i;
        S.emplace_back(i);
        x = pre[i];
    }
    reverse(S.begin(), S.end());
    return S;
}

Back to top page