Pythonで特定のリストの最長の算術サブシーケンスの長さを見つけるプログラム

numsと呼ばれる数値のリストがあるとすると、最長の算術サブシーケンスの長さを見つける必要があります。シーケンスS[i]は、S [i + 1] --S [i]が範囲内のすべてのiに対して同じ値を持つ場合の等差数列です（0≤i

したがって、入力がnums =[1、4、7、10、13、20、16]のような場合、出力は6になります。サブシーケンス[1、4、7、10、13、16]は算術演算です。連続する各要素の差が3であるためです。

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

• n：=arrのサイズ
• n <=1の場合、
  • return n
• res：=0
• dp：=空のマップ。デフォルトでは、キーが見つからない場合は1が格納されます
• 1からn-1の範囲のiの場合、do
  • 0からi-1の範囲のjの場合、do
    • diff：=arr [i] --arr [j]
    • dp [i、diff]：=dp [j、diff] + 1
    • res：=resとdp[i、diff
    の最大値
• return res

例（Python）

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

from collections import defaultdict
class Solution:
   def solve(self, arr):
      n = len(arr)
      if n <= 1:
         return n
      res = 0
      dp = defaultdict(lambda: 1)
      for i in range(1, n):
         for j in range(i):
            diff = arr[i] - arr[j]
            dp[i, diff] = dp[j, diff] + 1
            res = max(res, dp[i, diff])
      return res
ob = Solution()
nums = [1, 4, 7, 10, 13, 20, 16]
print(ob.solve(nums))

入力

[1, 4, 7, 10, 13, 20, 16]

出力

6