【アルゴリズム脳トレ】leetcode medium 300 longest increasing subsequence

こんにちは

今回の学びは

・ここで漸化式を作る、という作業をどういう風にすればいいのか？と考えて、漸化式が作れればdp問題

・漸化式にはどんな変数が必要か？という考える

・変数がわかったら表をとにかく書き出してみる（頭でぼんやり考えていることが、具体的に描けロジックの抜け漏れ、うまく行きそうにない部分がと浮かぶ）

・変数の管理が難しそうであれば、変数を減らそうとする考える

・dp問題でもO(n**2)は結構あるよ

・(※1) dp表と漸化式、しっかり設計（考え抜か）しないとバグを生む

問題は。。。

まずは入出力をしっかりおさえましょう。

入力は　unsortedな　配列です

Input: [10,9,2,5,3,7,101,18]

出力は　長さなのでintergerです。最大で連続何個の数字が昇順で並んでいますか。という

問題です

10, 9, 2, 5, 3, 7, 101, 18

だったら

2, 5, 7, 101の４個が昇順の最長です

O(n**2)的に10から舐めると、

10 < 101 => 2 , 9 < 101 | 18 => 2　お、この時点でちょっと怪しいぞ。101をスキップした場合の方が長くなる可能性がある。

ということは、O(n**2)ではなくてO(n * (2**n))が　総当たりのアルゴリズムとなりそうです

そうなると

O(2**n)は計算は nが２８くらいで計算の限界に達するので（アルゴリズムのビックOアナリシス　timespace analysisとそれぞれの許容入力サイズ大体一億ステップは１秒を目安にしている）

もっといい方法を考える必要がある

10, 9, 2, 5, 3, 7, 101, 18

だいぶ考えましたが、うまい解答が思いつきませんでした。ただのメモになりますが

どのような思考を試みたのか後で見直すように。前回のアルゴリズム脳トレ】leetcode medium 322 coin changeで得た

エクセルにdp表を書いてみるということはやってみました。なので成長しているとは思うのですが、正解までに届かず。

頑張って考えましたが、わかりませんでしたので
解説を見ます。https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/

arr= 10 9 2 5 3 7 101 18 6
L(i)

L(i) = 1 + max( L(j) ) where 0 < j < I and arr[j] < arr[i]

L(0)で　arr[i]はarr[0]で10です。 0 < j < 0は成り立たないので L(0) = 1
L(1)で arr[i]はarr[1]で9です。0< j < 1は成り立たないのでL(1) = 1
L(2)で　arr[i]はarr[2]で2です。 0 < j < 2は 1だけで arr[1] < arr[2] が成り立ちますので L(2) = 1 + L(1) = 2
L(3)で　arr[i]はarr[3]で5です。 0 < j < 3は [1,2]で arr[1](9) < arr[3](5)はダメ、arr[2](2) < arr[3](5)が成り立ちますので L(3)= 1 + L(2) = 3

10 9 2 5 3 7 101 18 6

ここまで解説を見たならば
言葉にまとめられそうだ。

10 9 2 5 3 7 101 18 6
1 1 1 2 2 3 4 4 4

自分より小さい値での最大+1を、その値での最大とする。

ここで漸化式を作る、という作業をどういう風にすればいいのか？これがdpを解く鍵であるような気がしていますので

それを脱線して調べてみます

漸化式はパターン探し、だからこそ一筋縄ではないし難しいのだ。でもパターンを覚えちゃえば

簡単なはず！という期待を胸に、漸化式の解き方を覚えるべく脱線します ->

L(i)をL(0~I) までのデータを入力とした時の最大とします
するとL( 3)というのは入力0~3なので [10, 9, 2, 5]を入力とした時の最大昇順数は？
ということにしよう。
そうした時に次のL(4)を考える、入力にindex4の3が増えましたと [10, 9, 2, 5] + [3]
となって時の最大昇順数は？どうなりますか？
・ここで考え方として持っておきたいのが、常に漸化式に持って生きるか？
つまりある一定の法則で　以前の答えから、現在の答えが導き出せる形
にできないか？
と考えます

これは難しい問題です
L(4)の場合は新しく [3]が増えることで最大昇順数は？どうなるのか？
細かいことを気にせず、俯瞰して考えることこうです
最大昇順数は新たに数字は一個増えたわけだから
１、増えるか ( L(3) + 1 )
２、変わらないか (L(3) )
の二択ですよね。

まずはこういう大きな枠で抑えるべきです。最初から細かい条件を考えてしま
すと、頭がこんがります
つまりは L(i) = L( I - 1) + 1 か L(i-1)
という漸化式が書けそうです

先ほども言いましたが、

ここで漸化式を作る、という作業をどういう風にすればいいのか？と考えてい

実際にそのように考える。つまりは漸化式が作れればdp問題だといってもいいでしょう。

漸化式で以前の答えが、次の解答に繋がるので、それはキャッシュしてなんぼだし、それはもうすでに

dpなんですよ。

なので繰り返しですが、問題をみたら漸化式を探してみましょう。これも超重要。見つかれば

それはdpで(も)解けます

L(3)の時に例に戻って [10, 9, 2, 5] の最大昇順数は 2, 5の並びで2 です。
その状態で [3]が追加されましたと、　3は [2, 5]の　最後つまりは i-1の
インデックスである5 より小さいので3が昇順になることはない
つまりは、[3]が増えても最大昇順数は変わらない、ということが言えそうです
そして
L(4)は L(3)と同様に L(4) = 2 という結果になります　さらにその時の最大昇順列は
2, 5ということになります。しかしここで矛盾に気づきます
[10, 9, 2, 5, 3]が入力の時の最大昇順数は確かに2ですが、最大昇順列は2, 3といった
方が良さそうです
ここで、保持しておかないといけない変数は
最大昇順数
最大昇順列
の二つかな、と思います。二つくらいないらいけそうですが、最大昇順列の更新
のロジックが、なんかパッと思いつきませんよね。

このどんな変数が必要か？という考え方は超重要です

ちょっと実際書いていってみましょう
ここで抑えておきたいのは、L(i) = L(i-1) + 1は　入力(i-1) < 入力(i) だったら成立す
る　という仮説に基づいたロジックとことです

こうやって実際に書いてみると
頭でぼんやり考えていることが、否が応でも、具体的に描ける必要ができます
すると、ロジックの抜け漏れ、うまく行きそうにない部分がと浮かんできます

今やった例で行くと、
新しい数字が出た時に i-1 の値と比較して最大昇順数の更新を行ったのですが
以下の例だとうまくいきません

二つ間違いが起こりました
人間が考えれば最大昇順列は2,3,4,8,10 と　5であるのに対し、はじき出した答え
は3 と　大きな乖離があります。これは
最大昇順列の更新がうまくできてないことに起因します

例えばここ
index 4に来た時入力(4) は 3 ですと
その時入力(i-1) = 入力(4-1) = 入力(3) = 5 ですと
{入力(3)} < { 入力(4) } は　5 < 3 ですの不成立となります。
しかしながら
できることであれば最大昇順列は [2, 3]に更新したい
ところです
これがこの問題の味噌で、如何に最大昇順列を保持更新できるか？！です。

はい
この[2, 5]ではなく[2,3]を保持するためには
現在の[2, 5]を舐めて、3を挿入します。そして長さは最大昇順数の2でカットし
ます。なので
[2,3,5]なんだけど先頭からカットされて [2,3]という状態になります

この作業を毎回やっていくので、実はO(n**2)ということになります。

これでも実装できるのですが、
ここまでくれば、もうしこし、うまく回せないか
とあと一押し考えれば
見えてくるものがあります

変数の管理が難しそうであれば、変数を減らそうとする考え方。これはdp問題に限らず

あらゆるアルゴリズム問題で有効です。変数が減れば、大抵は実装が簡単になるからです。

あと、今回のように、やり方は、減らし方が判らないパターン多いですよね。

私もほとんど湧いてきません。そういう時は今回のようにいったんやってみるも大切です、それで考えて

あとでオプティマイズしようという考え方でOKです。漸化式の考え方さえ合っていれば

実装の複雑度が変わるだけで、正解は出せます。やっているうちにはあるいは、やってみたら

他のアイデアが出てくることは往々にあります

それはこの最大昇順列を保持更新せずに、同様の情報が埋もれている
トイことです

それは
最初にいった、抑えておきたいロジックは

ここで抑えておきたいのは、L(i) = L(i-1) + 1は　入力(i-1) < 入力(i) だったら成立す
る　という仮説に基づいたロジックとことです

というものでした
これを
L(i) = L(i-1) + 1は　入力(i-1) < 入力(i) だったら成立

ではなく

L(i) = Max{ L([0,1,…,i-1]) } + 1は　 [0,1,…,i-1]をj とすると　　入力(j) < 入力(i) で最大のもとに+1するだったら成立

というします
若干、ややこしいですが、要は
新しい値入力(i)が増えた時に、以前の入力の中から良さげなやつを選んで、そいつをもとに新しい結果を作る
という手間を掛けてあげています

O(n**2)となるdpには、こういうもうひと舐め操作も有りなんです
ではその新しい考え方で、やってみましょう

ここまで考えつくせば、実装は簡単です

今回の解説は自分の試行錯誤を記しているので簡潔とは言えないので、今回の経験を踏まえ

もう一度、スッキリした頭で要所だけを解説する記事も描きたいと思います。

（あとでアップ　＝＞こちらです）

実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は　

pseudocode（擬似コード）をかいてみますか。

。。。

実際の実装はこちら

import logging
logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.basicConfig(level=logging.DEBUG, format="%(message)s")

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if nums is None or len(nums) == 0: return 0
        sz = len(nums)
        L = [0] * sz
        for i in range(sz):
            if i == 0:
                L[0] = 1
                logging.debug("%s:initially" % L)
                continue
            maxi = -1
            for j in range(0, i):
                if nums[j] < nums[i]:
                    maxi = max(L[j], maxi)
            if maxi != -1:
                # found
                L[i] = maxi + 1
            else:
                #L[i] = L[i-1]
                L[i] = 1
            logging.debug("%s" % L)

        return max(L)



samples = [
    # ([10,9,2,5,3,7,101,18], 4),
    # ([4,10,4,3,8,9], 3),
    ([1,3,6,7,9,4,10,5,6], 6)
]
for S, expected in samples:
    print("-"*20)
    ans = Solution().lengthOfLIS(S)
    assert ans == expected, "%s should be %s but %s" % (S, expected, ans)
    print("%s = %s as expected!" % (S, ans))

これだけ、事前に考えてdpの構造にも自信が合ったのですが

max(L(j))が見つからなかった場合

L(i) = L(i-1)　としてしまっていました

そこは max( L(j) ) が一つもないということは、L(i)がもっとも大きく、左側にそれより小さいものはない、つまり昇順になるはずがなく1を代入しなければなりませんでした

L[i] = 1　ですね。

dp設計漏れと表現しておきましょうか。※1

もういっちょ、ミスもありました

このケースでうまく通らず 1,3,6,7,9,4,10,5,6

理由は最後にdp表にここまでの最大昇順数が入るべきなのですが、

nums[j] < nums[i]をしているだけなので、最大は入ってこず、この数字が入れいました。これを含む最適解は幾つですか？

というような意味合いになる。つまり

Lの中から最大のものを返さねばならないとわかった。return L[i] ではなく

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if nums is None or len(nums) == 0: return 0
        sz = len(nums)
        L = [0] * sz
        for i in range(sz):
            if i == 0:
                L[0] = 1
                continue
            maxi = -1
            for j in range(0, i):
                if nums[j] < nums[i]:
                    maxi = max(L[j], maxi)
            if maxi != -1:
                L[i] = maxi + 1
            else:
                L[i] = 1
        return L[i]

return max(L)

となるべきだった。