Longest Increasing Subsequence (LIS)
(algo/sequence/lis.hpp)

• View this file on GitHub
• Last update: 2026-07-07 21:49:48+09:00
• Include: #include "algo/sequence/lis.hpp"

Overview

Returns the zero-based indices of a longest increasing subsequence. The indices can be used to recover the values or to align the result with parallel arrays.

The implementation uses a tails array and predecessor links. It uses std::lower_bound for a strict subsequence and std::upper_bound for a non-decreasing subsequence.

Template Parameters

• T: Element type. Values must be comparable using <.

Methods

Method	Description	Complexity
std::vector<int> lis(const std::vector<T>& a, bool strict = true)	Returns the indices of the LIS. If strict is true, finds a strictly increasing sequence. If false, allows adjacent elements in the sequence to be equal (non-decreasing).	$O(N \log N)$ time, $O(N)$ space

Example

#include "algo/sequence/lis.hpp"
#include <iostream>
#include <vector>

int main() {
    std::vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

    const std::vector<int> lis_indices = m1une::algo::lis(a);

    std::cout << "LIS length: " << lis_indices.size() << "\n"; // Output: 4

    std::cout << "Indices: ";
    for (int idx : lis_indices) std::cout << idx << " ";
    std::cout << "\n";

    std::cout << "Values: ";
    for (int idx : lis_indices) std::cout << a[idx] << " ";
    std::cout << "\n";

    const std::vector<int> non_decreasing = m1une::algo::lis(a, false);
    std::cout << "Non-decreasing length: " << non_decreasing.size() << "\n";

    return 0;
}

Required by

• Algorithms All (algo/all.hpp)
• Sequence Algorithms All (algo/sequence/all.hpp)

Verified with

• verify/algo/sequence/longest_increasing_subsequence.test.cpp
• verify/algo/sequence/sequence_algorithms.test.cpp

Code

#ifndef M1UNE_ALGO_SEQUENCE_LIS_HPP
#define M1UNE_ALGO_SEQUENCE_LIS_HPP 1

#include <algorithm>
#include <iterator>
#include <vector>

namespace m1une {
namespace algo {

// Returns the zero-based indices of a longest increasing subsequence.
// If `strict` is false, equal adjacent values are also allowed.
template <typename T>
std::vector<int> lis(const std::vector<T>& a, bool strict = true) {
    const int n = int(a.size());
    std::vector<T> tails;
    std::vector<int> tail_positions;
    std::vector<int> predecessor(n, -1);
    tails.reserve(n);
    tail_positions.reserve(n);

    for (int i = 0; i < n; ++i) {
        auto it = strict ? std::lower_bound(tails.begin(), tails.end(), a[i])
                         : std::upper_bound(tails.begin(), tails.end(), a[i]);
        const int length = int(std::distance(tails.begin(), it));

        if (it == tails.end()) {
            tails.push_back(a[i]);
            tail_positions.push_back(i);
        } else {
            *it = a[i];
            tail_positions[length] = i;
        }

        if (length > 0) {
            predecessor[i] = tail_positions[length - 1];
        }
    }

    if (tail_positions.empty()) return {};

    std::vector<int> result;
    result.reserve(tail_positions.size());
    int current = tail_positions.back();
    while (current != -1) {
        result.push_back(current);
        current = predecessor[current];
    }
    std::reverse(result.begin(), result.end());
    return result;
}

}  // namespace algo
}  // namespace m1une

#endif  // M1UNE_ALGO_SEQUENCE_LIS_HPP

#line 1 "algo/sequence/lis.hpp"



#include <algorithm>
#include <iterator>
#include <vector>

namespace m1une {
namespace algo {

// Returns the zero-based indices of a longest increasing subsequence.
// If `strict` is false, equal adjacent values are also allowed.
template <typename T>
std::vector<int> lis(const std::vector<T>& a, bool strict = true) {
    const int n = int(a.size());
    std::vector<T> tails;
    std::vector<int> tail_positions;
    std::vector<int> predecessor(n, -1);
    tails.reserve(n);
    tail_positions.reserve(n);

    for (int i = 0; i < n; ++i) {
        auto it = strict ? std::lower_bound(tails.begin(), tails.end(), a[i])
                         : std::upper_bound(tails.begin(), tails.end(), a[i]);
        const int length = int(std::distance(tails.begin(), it));

        if (it == tails.end()) {
            tails.push_back(a[i]);
            tail_positions.push_back(i);
        } else {
            *it = a[i];
            tail_positions[length] = i;
        }

        if (length > 0) {
            predecessor[i] = tail_positions[length - 1];
        }
    }

    if (tail_positions.empty()) return {};

    std::vector<int> result;
    result.reserve(tail_positions.size());
    int current = tail_positions.back();
    while (current != -1) {
        result.push_back(current);
        current = predecessor[current];
    }
    std::reverse(result.begin(), result.end());
    return result;
}

}  // namespace algo
}  // namespace m1une

Back to top page