Python での最長増加サブシーケンス

部分列とは何か、Python で n 乗法と二分探索法を使用して、配列から最長増加部分列を計算する方法を学びます。

N 乗法を使用して Python で最長増加部分列を計算する

有名な質問は、Python コミュニティ周辺で最も長く増加するサブシーケンスについて尋ねられ、さまざまなインタビューで尋ねられます。 これは Leetcode 問題であり、問題は次のように述べています: ソートされていない整数の配列が与えられ、与えられた配列の最も長く増加するサブシーケンスまたはサブセットの長さを見つけます。

サブセットは配列の短い配列のようなものです。 各配列は複数のサブセットを持つことができます。 もう1つのことは、部分配列がこの[10,9,2,5,3,7,101,18]配列の要素の一部になることですが、連続した部分列の方法です。

[2, 3, 5, 7] のようにすることはできますが、[2,3,101] にすることはできません。そのため、部分配列について説明するときにシーケンスを破る必要はありません。 そして、その後、要素が配列に現れる順序は同じでなければなりませんが、それはどの個人でもかまいません。

たとえば、この場合、ご覧のとおり、答えは [2, 3, 7,101] です。 5 はありませんが、サブシーケンスなので問題ありません。

[10,9,2,5,3,7,101,18] からの最長増加サブシーケンスを見ると、[2, 5, 7, 101] が見つかります。 これは答えを意味することもできますが、答えは [2, 3, 7, 101] である可能性もあり、これは私たちの他のサブシーケンスでもあります. [3, 7, 101] もサブシーケンスですが、それは最長ではないので考慮しません。

複数の組み合わせが存在する場合があります。 先ほど見たように、必要なのは長さだけです。

この例では、ゼロのインデックスから始まり、すべての異なるパスをたどる再帰的なソリューションを簡単に考えることができます。 この配列 [0,3,1,6,2,2,7] を使用すると、たとえば、0 を使用して 3 に移動したり、1 に移動したりできます。 6 へ。

そして、その時点から、再帰的に続行します。 次の例を見てください。どのパスが最も長く、指数関数的になりますか? 何らかの動的計画法のアプローチが必要であると簡単に考えることができます。

したがって、配列があり、これらの各インデックスには少なくとも 1つの長さがあります。

[0,3,1,6,2,2,7]
[1,1,1,1,1,1,1]

長さ 1 の最初のインデックス 0 から開始しますが、3 を使用すると、後ろを見ることができ、3 が 0 よりも大きい場合、3 の長さは 2 になります。 . 再び 1 を使用すると、現在のインデックスより前のすべてのインデックスの後ろを調べます。

ゼロのインデックスから、1 は 0 より大きく、1 は 3 より大きくないことがわかります。したがって、この時点で、0 と 1、およびそれらの長さを計算しています。 2になります。

[0,3,1,6,2,2,7]
[1,2,2,1,1,1,1]

6 について考えながら、最初から後ろを見てみましょう。6 は [0,1] または [0,3] よりも大きく、6 を含めると、その長さは 3 になります。 なら、2 の長さも 3 となり、これは 2 乗法です。

[0,3,1,6,2,2,7]
[1,2,2,3,3,...]

時間の複雑さと空間の複雑さ

コードに飛び込んで、CalculateSubSequence というクラスを作成しましょう。 lengthOfLIS 関数内で、nums_list 変数を初期化して nums の長さを 1 回だけの配列で初期化します。

ネストされたループ内で、値がチェックしている数値よりも大きいかどうかをチェックします。 次に、i の nums_list を取得してみましょう。nums_list[i] を使用して最大値を取得しながら、nums_list の値を更新します。

i は外側のループからの繰り返しの後に来て、 nums_list[j] は内側のループからの繰り返しの後に j が来て、それに 1 を追加します。 最後に、nums_list の最大値を返しています。

class CalculateSubSequence:
    def lengthOfLIS(self, nums: list[int]) -> int:

        nums_list = [1] * len(nums)

        for i in range(len(nums) - 1, -1, -1):

            for j in range(i + 1, len(nums)):

                if nums[i] < nums[j]:

                    nums_list[i] = max(nums_list[i], nums_list[j] + 1)

        return max(nums_list)


sbs = CalculateSubSequence()
sbs.lengthOfLIS([0, 3, 1, 6, 2, 2, 7])

ここで、時間計算量は n の 2 乗になり、空間計算量は n の o になります。

4

上記の解決策で十分ですが、別のアプローチ n log では、bisect_left を使用して一時配列の左側にバイナリ検索を使用します。

from bisect import bisect_left


class CalculateSubSequence:
    def lengthOfLIS(self, nums: list[int]) -> int:
        n = len(nums)
        tmp = [nums[0]]
        for n in nums:
            x = bisect_left(tmp, n)
            if x == len(tmp):
                tmp.append(n)
            elif tmp[x] > n:
                tmp[x] = n
        return len(tmp)


sbs = CalculateSubSequence()
sbs.lengthOfLIS([0, 3, 1, 6, 2, 2, 7])

出力：

4