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

numsと呼ばれる数値のリストがあり、最も長く増加するサブシーケンスの長さを見つける必要があり、サブシーケンスがリストの先頭に折り返される可能性があると想定しています。

したがって、入力がnums =[6、5、8、2、3、4]の場合、最長増加部分列は[2、3、4、6、8]であるため、出力は5になります。

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

• a：=numsの2倍のサイズのリストを作成し、numsを2回入力します
• ans：=0
• 0からnumsのサイズの範囲のiの場合は、
  • dp：=新しいリスト
  • 範囲iからnums+i-1のサイズのjの場合、do
    • n：=a [j]
    • k：=dpにnを挿入するために最も左のインデックス
    • kがdpのサイズと同じである場合、
      • dpの最後にnを挿入
    • それ以外の場合、
      • dp [k]：=n
    • ans：=ansの最大値とdpのサイズ
• 回答を返す

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

例

import bisect
class Solution:
   def solve(self, nums):
      a = nums + nums
      ans = 0
      for i in range(len(nums)):
         dp = []
         for j in range(i, len(nums) + i):
            n = a[j]
            k = bisect.bisect_left(dp, n)
            if k == len(dp):
               dp.append(n)
            else:
               dp[k] = n
         ans = max(ans, len(dp))
      return ans

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

入力

[4, 5, 8, 2, 3, 4]

出力

5