Longest Increasing Subsequence
(lib/dp/LIS.hpp)

• View this file on GitHub
• Last update: 2024-05-04 18:06:16+09:00
• Include: #include "lib/dp/LIS.hpp"

Longest Increasing Subsequence

概要

配列の最長増加部分列の長さを求めます。

$dp[i]$: 長さが i の増加部分列として最後尾の要素のとりうる最小値 とすると計算できる。

使い方

• LIS(a, is_strong): 配列 a の最長増加部分列の長さを求めます。(is_strong = false のとき、広義最長増加部分列)
• construct_LIS(a, is_strong): 配列 a の最長増加部分列を構築します。

計算量

配列の要素数を $N$ とする。

• LIS(a, is_strong): $\mathrm{O}(N \log N)$
• construct_LIS(a, is_strong): $\mathrm{O}(N \log N)$

Verified with

• test/library_checker/other/longest_increasing_subsequence.test.cpp

Code

#pragma once

/**
 * @brief Longest Increasing Subsequence
 * @docs docs/dp/LIS.md
 */

template <typename T>
int LIS(vector<T> a, bool is_strong = true){
    const long long INF = 0x1fffffffffffffff;
    int n = (int) a.size();
    vector<long long> dp(n, INF);
    for(int i = 0; i < n; ++i){
        if(is_strong) *lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
        else *upper_bound(dp.begin(), dp.end(), a[i]) = a[i];
    }
    return lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
}

template <typename T>
vector<int> construct_LIS(vector<T> a, bool is_strong = true){
    const long long INF = 0x1fffffffffffffff;
    int n = (int) a.size();
    vector<long long> dp(n, INF);
    vector<vector<int>> idx(n);
    for(int i = 0; i < n; ++i){
        if(is_strong){
            auto iter = lower_bound(dp.begin(), dp.end(), a[i]);
            *iter = a[i];
            idx[(int) (iter - dp.begin())].emplace_back(i);
        } else{
            auto iter = upper_bound(dp.begin(), dp.end(), a[i]);
            *iter = a[i];
            idx[(int) (iter - dp.begin())].emplace_back(i);
        }
    }
    int k = lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
    vector<int> res;
    int now = n;
    for(int i = k - 1; i >= 0; --i){
        auto iter = upper_bound(idx[i].begin(), idx[i].end(), now);
        iter--;
        now = *iter;
        res.push_back(now);
    }
    reverse(res.begin(), res.end());
    return res;
}

#line 2 "lib/dp/LIS.hpp"

/**
 * @brief Longest Increasing Subsequence
 * @docs docs/dp/LIS.md
 */

template <typename T>
int LIS(vector<T> a, bool is_strong = true){
    const long long INF = 0x1fffffffffffffff;
    int n = (int) a.size();
    vector<long long> dp(n, INF);
    for(int i = 0; i < n; ++i){
        if(is_strong) *lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
        else *upper_bound(dp.begin(), dp.end(), a[i]) = a[i];
    }
    return lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
}

template <typename T>
vector<int> construct_LIS(vector<T> a, bool is_strong = true){
    const long long INF = 0x1fffffffffffffff;
    int n = (int) a.size();
    vector<long long> dp(n, INF);
    vector<vector<int>> idx(n);
    for(int i = 0; i < n; ++i){
        if(is_strong){
            auto iter = lower_bound(dp.begin(), dp.end(), a[i]);
            *iter = a[i];
            idx[(int) (iter - dp.begin())].emplace_back(i);
        } else{
            auto iter = upper_bound(dp.begin(), dp.end(), a[i]);
            *iter = a[i];
            idx[(int) (iter - dp.begin())].emplace_back(i);
        }
    }
    int k = lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
    vector<int> res;
    int now = n;
    for(int i = k - 1; i >= 0; --i){
        auto iter = upper_bound(idx[i].begin(), idx[i].end(), now);
        iter--;
        now = *iter;
        res.push_back(now);
    }
    reverse(res.begin(), res.end());
    return res;
}

Back to top page