====== seqtask.py ======

===== imports and globals =====
<dkpr py>
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
</dkpr>


===== longest_inc_subseq_length / longest_dec_subseq_length =====

==== 코드 ====
<dkpr py>
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)
</dkpr>

<dkpr py>
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)
</dkpr>

==== 설명 ====
  * [[ps:tutorial:lis]] 참고

==== 이 코드를 사용하는 문제 ====
---- struct table ----
schema: ps
cols: site, prob_id, %title%, prob_level
filter: teflib ~ *[seqtask.longest_inc_subseq_length]*
filteror: teflib ~ *[seqtask.longest_dec_subseq_length]*
csv: 0
----


===== longest_inc_subseq_length_by_last_elem / longest_dec_subseq_length_by_last_elem =====

==== 코드 ====
<dkpr py>
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
</dkpr>

<dkpr py>
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
</dkpr>

==== 설명 ====
  * [[ps:tutorial:lis]] 참고

==== 이 코드를 사용하는 문제 ====
---- struct table ----
schema: ps
cols: site, prob_id, %title%, prob_level
filter: teflib ~ *[seqtask.longest_inc_subseq_length_by_last_elem]*
filteror: teflib ~ *[seqtask.longest_dec_subseq_length_by_last_elem]*
csv: 0
----