最長増加部分列問題 (LIS) って何（＾～＾）！？

「　分からない問題ばかりだしな。分からなくても普通だよな」

「　しかし　分からない問題は出てくる」

「　じゃあ　最長増加部分列問題（LIS; Longest Increase Subsequence）を調べましょう！」

「　何だぜ、それ？」

「　👆　身長を測る線みたいなものを用意しましょう」

「　👆　横軸に　好きな数列を書くとしましょう」

「　👆　棒グラフを描いておくと　大きさの比較をしやすいでしょう」

「　👆　例えば　上図のように線をつなげば　(1, 2, 3, 5, 8)　という長さ５の数列が作れるわね」

「　そういう数列で　一番長いやつを作ればいいのかだぜ？」

「　じゃあ　まず　一番小さいやつを探そうぜ？」

「　👆　２つあるけど」

「　１番左のやつが　よくないか？」

「　👆　じゃあ　こいつで確定だな」

「　じゃあ次は　そいつより大きいやつの中で　一番小さいやつを探そうぜ？」

「　👆　２だぜ」

「　以下同様で　やってみてくれだぜ」

「　👆　３が　２つあるんだけど」

「　２　より　左側は　見なくてよくない？」

「　👆　じゃあ　３　は　こっちだな。　その左の　５と　８も　確定だろ」

「　アルゴリズムは　簡単に作れたな」

「　そんな簡単なもの　問題で出してくるかなあ？」

# Longest increase subsequence

cards = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8]
subseq = []

# 1周目
minimum = 999
min_index = -1

for i in range(0, len(cards)):
    if cards[i] < minimum:
        minimum = cards[i]
        min_index = i
    pass

print(f"(1周目) minimum={minimum} min_index={min_index}")

# 2周目
pre_minimum = minimum
minimum = 999

for i in range(min_index, len(cards)):
    if pre_minimum < cards[i] and cards[i] < minimum:
        minimum = cards[i]
        min_index = i
    pass

print(f"(2周目) minimum={minimum} min_index={min_index}")

# 3周目
pre_minimum = minimum
minimum = 999

for i in range(min_index, len(cards)):
    if pre_minimum < cards[i] and cards[i] < minimum:
        minimum = cards[i]
        min_index = i
    pass

print(f"(3周目) minimum={minimum} min_index={min_index}")

# 4周目
pre_minimum = minimum
minimum = 999

for i in range(min_index, len(cards)):
    if pre_minimum < cards[i] and cards[i] < minimum:
        minimum = cards[i]
        min_index = i
    pass

print(f"(4周目) minimum={minimum} min_index={min_index}")

# 5周目
pre_minimum = minimum
minimum = 999

for i in range(min_index, len(cards)):
    if pre_minimum < cards[i] and cards[i] < minimum:
        minimum = cards[i]
        min_index = i
    pass

print(f"(5周目) minimum={minimum} min_index={min_index}")

(1周目) minimum=1 min_index=1
(2周目) minimum=2 min_index=6
(3周目) minimum=3 min_index=9
(4周目) minimum=5 min_index=10
(5周目) minimum=8 min_index=11

「　👆　決め打ちのベタ書きなら　こうだけど」

「　１周目と、２周目以降を　同じ書き方にできないの？」

# Longest increase subsequence

cards = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8]
subseq = []
min_index = 0
minimum = -1

# 1周目
pre_minimum = minimum
minimum = 999

for i in range(min_index, len(cards)):
    if pre_minimum < cards[i] and cards[i] < minimum:
        minimum = cards[i]
        min_index = i
    pass

print(f"(1周目) minimum={minimum} min_index={min_index}")

# 2周目
pre_minimum = minimum
minimum = 999

for i in range(min_index, len(cards)):
    if pre_minimum < cards[i] and cards[i] < minimum:
        minimum = cards[i]
        min_index = i
    pass

print(f"(2周目) minimum={minimum} min_index={min_index}")

# 3周目
pre_minimum = minimum
minimum = 999

for i in range(min_index, len(cards)):
    if pre_minimum < cards[i] and cards[i] < minimum:
        minimum = cards[i]
        min_index = i
    pass

print(f"(3周目) minimum={minimum} min_index={min_index}")

# 4周目
pre_minimum = minimum
minimum = 999

for i in range(min_index, len(cards)):
    if pre_minimum < cards[i] and cards[i] < minimum:
        minimum = cards[i]
        min_index = i
    pass

print(f"(4周目) minimum={minimum} min_index={min_index}")

# 5周目
pre_minimum = minimum
minimum = 999

for i in range(min_index, len(cards)):
    if pre_minimum < cards[i] and cards[i] < minimum:
        minimum = cards[i]
        min_index = i
    pass

print(f"(5周目) minimum={minimum} min_index={min_index}")

「　👆　工夫して　こうだな」

「　じゃあ　５回ループで　おまとめ　できるのでは？」

# Longest increase subsequence

cards = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8]
subseq = []
min_index = 0
minimum = -1

for j in range(0, 5):
    pre_minimum = minimum
    minimum = 999

    for i in range(min_index, len(cards)):
        if pre_minimum < cards[i] and cards[i] < minimum:
            minimum = cards[i]
            min_index = i
        pass

    print(f"({j}周目) minimum={minimum} min_index={min_index}")

「　👆　まったく　すっきり　だぜ」

「　停止条件って何なの？　５　じゃなくて、自動で判定するには」

「　minimum　なやつが　見つからなかったら　停止すればいいんじゃないか？」

# Longest increase subsequence

cards = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8]
subseq = []
min_index = 0
minimum = -1
count = 1

while True:
    pre_minimum = minimum
    minimum = 999

    for i in range(min_index, len(cards)):
        if pre_minimum < cards[i] and cards[i] < minimum:
            minimum = cards[i]
            min_index = i
        pass

    # 停止条件
    if minimum == 999:
        break

    print(f"({count}周目) minimum={minimum} min_index={min_index}")
    count += 1

「　👆　ほい」

「　これだと多分　二重ループだから　O(n^2)　なんで、 TLE　になるのよ」

「　どうすれば……」