最長増加部分列 (longest increasing subsequence)
(DP/lis.py)

• View this file on GitHub
• Last update: 2023-03-03 23:23:30+09:00

概要

最長増加部分列を求めるアルゴリズム。

使い方

lis(array: Sequence[int], strict: bool = True) -> List[int]
array に対する最長増加部分列を返す。strict=False とすると、広義最長増加部分列を返す。計算量 $O(N \log N)$

Verified with

• TestCase/AOJ/DPL_1_D.test.py
• TestCase/LibraryChecker/longest_increasing_subsequence.test.py

Code

from bisect import bisect_left, bisect_right


def lis(array, strict=True):
    bisect_ = bisect_left if strict else bisect_right
    tmp = []
    idxs = [0] * len(array)

    for i, val in enumerate(array):
        idx = bisect_(tmp, val)
        if idx == len(tmp):
            tmp.append(val)
        else:
            tmp[idx] = val
        idxs[i] = idx

    lis_array = []
    j = len(tmp) - 1
    for i, val in reversed(list(enumerate(array))):
        if idxs[i] == j:
            lis_array.append(val)
            j -= 1
    return lis_array[::-1]


def lis_index(array, strict=True):
    lis_array = lis(array, strict)
    idxs = []

    i = 0
    for idx, val in enumerate(array):
        if i < len(lis_array) and lis_array[i] == val:
            idxs.append(idx)
            i += 1
    return idxs

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page