Pythonで一定の差がある最長の算術サブシーケンスの長さを見つけるプログラム

数値のリストnumsと別の値diffがあるとすると、サブシーケンス内の連続する数値の差がdiffと同じである、最長の算術サブシーケンスの長さを見つける必要があります。

したがって、入力がnums =[-1、1、4、7、2、10] diff =3のような場合、出力は4になります。これは、[1、4、7、10のようなサブシーケンスを選択できるためです。 ]。

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

• seen：=空の辞書、キーが存在しない場合のデフォルト値は0です
• mx：=0
• numsのxごとに、
  • x --diffが表示されている場合は、
    • sawed [x]：=saw [x --diff] + 1
  • それ以外の場合、
    • sawed [x]：=1
  • mx：=mxの最大値とseen[x]
• return mx

例

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

from collections import defaultdict
def solve(nums, diff):
   seen = defaultdict(int)
   mx = 0
   for x in nums:
      if x - diff in seen:
         seen[x] = seen[x - diff] + 1
      else:
         seen[x] = 1
      mx = max(mx, seen[x])
   return mx

nums = [-1, 1, 4, 7, 2, 10]
diff = 3
print(solve(nums, diff))

入力

[-1, 1, 4, 7, 2, 10], 3

出力

4