import bisect
import operator

from collections.abc import Hashable, Iterable, Reversible, Sequence
from typing import Any, Literal
from teflib.common.types import Sortable, Index, Count

def longest_inc_subseq_length[T: Sortable](
    seq: Iterable[T], *, strict: bool = False
) -> Count:
    """Compute length of LIS of given sequence."""
    bisect_func = bisect.bisect_left if strict else bisect.bisect_right
    comp_func = operator.gt if strict else operator.ge
    seq_iter = iter(seq)
    if (first_elem := next(seq_iter, None)) is None:
        return 0
    last_elem_by_len = [first_elem]
    for elem in seq_iter:
        if comp_func(elem, last_elem_by_len[-1]):
            last_elem_by_len.append(elem)
        else:
            last_elem_by_len[bisect_func(last_elem_by_len, elem)] = elem
    return len(last_elem_by_len)

def longest_dec_subseq_length[T: Sortable](
    seq: Reversible[T], *, strict: bool = False
) -> Count:
    """Compute length of LDS of given sequence."""
    return longest_inc_subseq_length(reversed(seq), strict=strict)

• 가장 긴 증가하는 부분 수열 (LIS; Longest Increasing Subsequence) 참고

def longest_inc_subseq_length_by_last_elem[T: Sortable](
    seq: Sequence[T], *, strict: bool = False
) -> list[Count]:
    """Returns a list L, where L[i] is length of LIS that ends with seq[i]."""
    if not seq:
        return []
    bisect_func = bisect.bisect_left if strict else bisect.bisect_right
    comp_func = operator.gt if strict else operator.ge
    seq_iter = iter(seq)
    last_elem_by_len, lengths, l = [next(seq_iter)], [1], 1
    for elem in seq_iter:
        if comp_func(elem, last_elem_by_len[-1]):
            last_elem_by_len.append(elem)
            l += 1
            lengths.append(l)
        else:
            ind = bisect_func(last_elem_by_len, elem)
            last_elem_by_len[ind] = elem
            lengths.append(ind + 1)
    return lengths

def longest_dec_subseq_length_by_last_elem[T: Sortable](
    seq: Sequence[T], *, strict: bool = False
) -> list[Count]:
    """Returns a list L, where L[i] is length of LDS that ends with seq[i]."""
    if not seq:
        return []
    bisect_func = bisect.bisect_right if strict else bisect.bisect_left
    comp_func = operator.lt if strict else operator.le
    seq_iter = iter(seq)
    last_elems: list[Any] = [None] * len(seq)
    last_elems[-1] = next(seq_iter)
    lengths, beg, end = [1], len(seq) - 1, len(seq)
    for elem in seq_iter:
        if comp_func(elem, last_elems[beg]):
            beg -= 1
            last_elems[beg] = elem
            lengths.append(end - beg)
        else:
            ind = bisect_func(last_elems, elem, beg, end) - 1
            last_elems[ind] = elem
            lengths.append(end - ind)
    return lengths

• 가장 긴 증가하는 부분 수열 (LIS; Longest Increasing Subsequence) 참고