Sequence/Longest_Increasing_Subsequence.py

• View this file on GitHub
• Last update: 2024-08-31 23:52:58+09:00

Verified with

• test_verify/yosupo_library_checker/Data_Structure/Longest_Increasing_Subsequence.test.py

Code

def Longest_Increasing_Subsequence(A, equal = False):
    """ A に対する LIS (最大狭義単調増加列) を求める

    Args:
        A (list): 列
        equal (bool, optional): True にすると, LIS の条件が最大広義単調増加列になる. Defaults to False.

    Returns:
        dict:
            length: 最大単調増加列の長さ
            example: 最大単調増加列の例
            index: example においてそれぞれの項を持ってきたインデックス
    """
    if equal:
        from bisect import bisect_right as bis
    else:
        from bisect import bisect_left as bis

    L = []
    ind = [0] * len(A)

    for i, a in enumerate(A):
        k = bis(L,a)
        if k == len(L):
            L.append(a)
        else:
            L[k] = a

        ind[i]=k

    X = []
    I = []
    j = len(L)-1
    for i in range(len(A) - 1, -1, -1):
        if ind[i] == j:
            j -= 1
            X.append(A[i])
            I.append(i)

    X.reverse(); I.reverse()
    return { 'length': len(X), 'example': X, 'index': I }

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/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.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page