Longest Increasing Subarray

# Longest Increasing Subarray：最長増加部分列問題

長さ$N$の数列が与えられたとき，そのうちいくつかの項を順番を変えずに取り出して部分列を作る．これら部分列のうち，それが増加列であるようなものの中で，最大の長さを求めよ．

1
2
[3, 5, 2, 6, 7, 1, 4]
-> [3, 5, 6, 7] (len = 4)

# 解法

# $O(2^N \times N)$な力技

考えられる部分列を全て列挙し，それぞれが増加列であるかを調べる．部分列の列挙に$O(2^N)$，ある部分列が増加列であるかを調べるのに$O(N)$かかる．

再帰で全探索．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
lst = [3, 5, 2, 6, 7, 1, 4] # => 4

def LIS(lst):
    subs = []
    def rec(pos, sofar):
        if pos == len(lst):
            subs.append(sofar)
            return
        rec(pos + 1, sofar)
        rec(pos + 1, sofar + [lst[pos]])
    rec(0, [])
    def is_increasing(lst):
        for i in range(len(lst) - 1):
            if lst[i] > lst[i + 1]:
                return False
        return True
    ans = 0
    for sub in subs:
        if is_increasing(sub):
            ans = max(ans, len(sub))
    return ans

print(LIS(lst))

ビット全探索．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
lst = [3, 5, 2, 6, 7, 1, 4] # => 4

def LIS(lst):
    ans = 0

    def is_increasing(lst):
        for i in range(len(lst) - 1):
            if lst[i] > lst[i + 1]:
                return False
        return True

    for i in range(1 << len(lst)):
        sub = []
        for j in range(len(lst)):
            if i & (1 << j):
                sub.append(lst[j])
        if is_increasing(sub):
            ans = max(ans, len(sub))
    return ans

print(LIS(lst))

# $O(N^2)$で解く DP

dp[i]を「lst[i]が右端となるような増加部分列の最大の長さ」とすると，dp[i + 1]は「j < i + 1かつlst[j] <= lst[i + 1]なjについてのdp[j]の最大値 + 1」と更新できる．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
lst = [3, 5, 2, 6, 7, 1, 4] # => 4

def LIS(lst):
    # dp[i]: lst[i]が右端となるような増加部分列の最大の長さ
    dp = [1 for _ in range(len(lst))]
    for i in range(len(lst)):
        for j in range(i):
            if lst[j] <= lst[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

print(LIS(lst))

# $O(N^2)$で解く DP

一つ前のと添字を逆転させる．つまり，dp[i]を「長さi + 1の増加部分列のうちの最小の右端」とする．dp[i+1]はdp[i]より大きい最小のlst要素．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
lst = [3, 5, 2, 6, 7, 1, 4] # => 4

def LIS(lst):
    # dp[i]: 長さがi+1の増加部分列の最小の右端
    INF = float('inf')
    dp = [INF for _ in range(len(lst))]
    for i in range(len(lst)):
        for j in range(len(dp)):
            if j == 0 or dp[j - 1] < lst[i]:
                dp[j] = min(dp[j], lst[i])
    ans = 0
    for i in range(len(dp)):
        if dp[i] < INF:
            ans = i
    ans += 1
    return ans

print(LIS(lst))

# $O(N \log N)$で解く DP

dp[j]ごとにそこに入れるべきlst要素を決めるのでなくて，lst要素ごとにdpのどこに入れるべきなのかを二分探索で計算する．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
lst = [3, 5, 2, 6, 7, 1, 4] # => 4

from bisect import bisect_left

def LIS(lst):
    # dp[i]: 長さがi+1の増加部分列の最小の右端
    INF = float('inf')
    dp = [INF for _ in range(len(lst))]
    for i in range(len(lst)):
        dp[bisect_left(dp, lst[i])] = lst[i]
    return bisect_left(dp, INF)

print(LIS(lst))