[Python] 最長増加部分列(LIS)問題

ほぼ以下の内容です。

GeeksForGeeks Python program for Longest Incresing Subsequence

最長増加部分列(LIS: Longest Increasing Subsequence)問題

最長増加部分列(LIS: Longest Increasing Subsequence)問題とは、与えられた配列の中で、増加順に並んでいる最も長い部分列を見つける問題です。

例

• [10, 22, 9, 33, 21, 50, 41, 60, 80]の時、LIS は[10, 22, 33, 50, 60, 80]、長さ6です。
• [3, 10, 2, 1, 20]の時、LISは[3, 10, 20]、長さは3です。
• [3, 2]の時、LISは[3]または[2]、長さは1です。
• [50, 3, 10, 7, 40, 80]の時、LISは[3, 7, 40, 80]、長さは4 です。

再帰

arr[0..n-1]の配列が与えられた時、arr[i]をLISの最後の要素、L(i)をLISの長さとする。

するとL(i)は再帰的に下のように書くことができる。

L(i) = 1 + max( L(j) ) 　ただし、0 < j < i かつarr[j] < arr[i]の時。または、
L(i) = 1

## 最大値を保存する。
global maximum

def rec_lis(arr, n):
    # グローバル変数にアクセスする。
    global maximum
    # 終了条件
    if n == 1:
        return 1
    # 要素arr[n-1]で終わるLISの長さ
    max_ending_here = 1

    # arr[0], arr[1] ... arr[n-2]と再帰的に全てのLISを得る。
    for i in range(1, n):
        res = rec_lis(arr, i)
        if arr[i -1] < arr[n - 1] and res + 1 > max_ending_here:
            max_ending_here = res + 1
    # 全体の最大値の更新
    maximum = max(maximum, max_ending_here)

    return max_ending_here

def lis(arr):

    global maximum

    n = len(arr)
    maximum = 1
    rec_lis(arr, n)

    return maximum


arr = [10, 22, 9, 33, 21, 50, 41, 60]
print(lis(arr))

DP

def lis(arr):
    n = len(arr)

    # dp
    lis = [1] * n

    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1
    
    maximum = 0
    for i in range(n):
        maximum = max(maximum, lis[i])
    
    return maximum

arr = [10, 22, 9, 33, 21, 50, 41, 60]
print(lis(arr))