cp_library/alg/dp/lis_fn.py

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+09:00

Depends on

• cp_library/alg/dp/chmin_fn.py
• cp_library/alg/dp/max2_fn.py

Verified with

• test/library-checker/other/longest_increasing_sequence.test.py

Code

import cp_library.__header__
from bisect import bisect_left
import cp_library.alg.__header__
import cp_library.alg.dp.__header__
from cp_library.alg.dp.max2_fn import max2
from cp_library.alg.dp.chmin_fn import chmin

def lis(A: list):
    N = len(A)
    mn, mx = min(A), max(A)
    dp, idx, prev = [mx+1]*(N+1), [-1]*(N+1), [-1]*N
    dp[0], r = mn-1, 0
    for i,a in enumerate(A):
        if chmin(dp, p := bisect_left(dp,a,hi=r+1), a):
            idx[p], prev[i], r = i, idx[p-1], max2(r,p)
    ans, i = [0]*r, idx[r]
    for j in range(r-1,-1,-1): ans[j], i = i, prev[i]
    return ans

    

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''
from bisect import bisect_left



def max2(a, b):
    return a if a > b else b

def chmin(dp, i, v):
    if ch:=dp[i]>v:dp[i]=v
    return ch

def lis(A: list):
    N = len(A)
    mn, mx = min(A), max(A)
    dp, idx, prev = [mx+1]*(N+1), [-1]*(N+1), [-1]*N
    dp[0], r = mn-1, 0
    for i,a in enumerate(A):
        if chmin(dp, p := bisect_left(dp,a,hi=r+1), a):
            idx[p], prev[i], r = i, idx[p-1], max2(r,p)
    ans, i = [0]*r, idx[r]
    for j in range(r-1,-1,-1): ans[j], i = i, prev[i]
    return ans

    

Back to top page