Pythonで最長増加部分列の長さを見つけるプログラム

番号のリストがあるとします。最も長く増加するサブシーケンスの長さを見つける必要があります。したがって、入力が[6、1、7、2、8、3、4、5]の場合、最長増加部分列は[2,3,4,5,6]であるため、出力は5になります。

これを解決するには、次の手順に従います-

• サイズがnumsと同じであるtailsという配列を作成し、これを0で埋めます。

• サイズ：=0

• nums配列の各要素xについて-

  • i：=0、j：=サイズ

  • iはjと同じではありませんが、

    • mid：=i +（j – i）/ 2

    • tails [mid]

  • tails [i]：=x

  • サイズ：=最大ofi+1およびサイズ

• 返品サイズ。

理解を深めるために、次の実装を見てみましょう-

例

class Solution(object):
   def solve(self, nums):
      tails =[0 for i in range(len(nums))]
      size = 0
      for x in nums:
         i=0
         j=size
         while i!=j:
            mid = i + (j-i)//2
            if tails[mid]> x:
               i= mid+1
            else:
               j = mid
         tails[i] = x
         size = max(i+1,size)
      return size

ob = Solution()
nums = [7, 2, 8, 3, 9, 4, 5, 6]
print(ob.solve(nums))

入力

[7, 2, 8, 3, 9, 4, 5, 6]

出力

5