"""
p58 — Longest Increasing Subsequence (LeetCode 300, MEDIUM).

Strictly increasing subsequence (not contiguous).

lis_n2          — O(n^2) DP.
lis_n_log_n     — O(n log n) patience sort.
lis_reconstruct — patience sort + predecessor pointers (returns the actual LIS).
lis_brute       — all subsequences; exponential.
"""
from __future__ import annotations
import random
from bisect import bisect_left
from typing import List


def lis_n2(nums: List[int]) -> int:
    n = len(nums)
    if n == 0:
        return 0
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
    return max(dp)


def lis_n_log_n(nums: List[int]) -> int:
    # INVARIANT: tails[k] = smallest tail value of any inc. subseq. of length k+1
    # seen in prefix processed so far. tails is sorted strictly increasing.
    tails: List[int] = []
    for x in nums:
        pos = bisect_left(tails, x)   # strict LIS -> bisect_left
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)


def lis_reconstruct(nums: List[int]) -> List[int]:
    n = len(nums)
    if n == 0:
        return []
    tails: List[int] = []
    tails_idx: List[int] = []   # tails_idx[k] = index in nums of the value at tails[k]
    prev: List[int] = [-1] * n
    for i, x in enumerate(nums):
        pos = bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
            tails_idx.append(i)
        else:
            tails[pos] = x
            tails_idx[pos] = i
        prev[i] = tails_idx[pos - 1] if pos > 0 else -1
    # Walk back from the last appended index
    result: List[int] = []
    k = tails_idx[-1]
    while k != -1:
        result.append(nums[k])
        k = prev[k]
    result.reverse()
    return result


def lis_brute(nums: List[int]) -> int:
    n = len(nums)
    best = 0
    for mask in range(1 << n):
        prev = -10**18
        length = 0
        ok = True
        for i in range(n):
            if mask & (1 << i):
                if nums[i] <= prev:
                    ok = False
                    break
                prev = nums[i]
                length += 1
        if ok:
            best = max(best, length)
    return best


def _is_strict_inc_subseq(sub: List[int], full: List[int]) -> bool:
    # Check `sub` is a strictly-increasing subseq of `full`.
    i = 0
    for v in full:
        if i < len(sub) and v == sub[i]:
            i += 1
    if i != len(sub):
        return False
    for j in range(1, len(sub)):
        if sub[j] <= sub[j - 1]:
            return False
    return True


def edge_cases() -> None:
    assert lis_n2([]) == 0
    assert lis_n_log_n([]) == 0
    assert lis_n_log_n([5]) == 1
    assert lis_n_log_n([10, 9, 2, 5, 3, 7, 101, 18]) == 4
    assert lis_n2([10, 9, 2, 5, 3, 7, 101, 18]) == 4
    assert lis_n_log_n([0, 1, 0, 3, 2, 3]) == 4
    assert lis_n_log_n([7, 7, 7, 7]) == 1
    assert lis_n_log_n([1, 2, 3, 4, 5]) == 5
    assert lis_n_log_n([5, 4, 3, 2, 1]) == 1
    rec = lis_reconstruct([10, 9, 2, 5, 3, 7, 101, 18])
    assert len(rec) == 4 and _is_strict_inc_subseq(rec, [10, 9, 2, 5, 3, 7, 101, 18])
    assert lis_reconstruct([]) == []
    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    for trial in range(500):
        n = rng.randint(0, 12)
        nums = [rng.randint(-5, 5) for _ in range(n)]
        a = lis_n2(nums)
        b = lis_n_log_n(nums)
        c = lis_brute(nums)
        rec = lis_reconstruct(nums)
        d = len(rec)
        assert a == b == c == d, f"trial {trial}: nums={nums} n2={a} nlogn={b} brute={c} rec={d}"
        if nums:
            assert _is_strict_inc_subseq(rec, nums), f"reconstruction invalid: nums={nums} rec={rec}"
    print("stress_test: 500 trials — n2, nlogn, brute, reconstruct agree and rec is valid.")


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")