最長増分シーケンス(LIS)

7036 ワード
パイ LIS DP テキストリンク
最長増分シーケンス(LIS).
与えられた数列内で最も長い部分数列を検索するアルゴリズム.
以下の数列では、LISは[10,20,50,90]または[10,20,40,60]である.

1.dpを用いて実施する.
最も簡単な実現、最も直感的です.しかし,それはO(N 2)O(N^2)O(N 2)の時間的複雑さを有し,従って適切に大きいNに対してTLEを行うことができる.
for i in range(N):
    if dp[i] == 0:
        dp[i] = 1
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i],dp[j]+1)
2.dp+バイナリ検索による実装
LISを解くことは最適な時間複雑度を持つアルゴリズムである.O(Nlogn)O(Nlogn)O(Nlogn)O(Nlogn)の時間的複雑さを有する.
プロセスは次のとおりです.
-LIS配列を挿入して昇順を維持し、配列内の各要素を巡回します.
-binary searchを使用します.

  • アレイ内の要素がLISアレイの最近接値(最後の値)より大きい場合は、最後に追加します.


  • アレイ内の要素がLISのアレイの最も近い値(最後の値)より小さい場合、binary searchによってアレイ内の要素をLISアレイに入れる位置を見つけることができます.(LISは昇順に並んでいるからです.)位置が見つかったら、元のLIS配列の値とスワップします.


  • 以上の手順を繰り返してLISを充填し、arr配列全体にわたってLISの長さをLISの長さとする.
    • from bisect import bisect_left

N = 100000

def LIS(n):
    maxVal = 0

    for i in range(n):
        if i == 0 or lis[-1] < arr[i]:
            lis.append(arr[i])
            trace[i] = len(lis)-1
            maxVal = trace[i]
        else:
            pos = bisect_left(lis, arr[i])
            lis[pos] = arr[i]
            trace[i] = pos
    print(maxVal+1)

    res = []
    for i in range(n-1,-1,-1):
        if trace[i] == maxVal:
            res.append(arr[i])
            maxVal -= 1
    res.reverse()
    print(*res)
    Event
    FragmentでonKeyDownイベントを傍受する