在Python中查找给定列表的最长算术子序列长度

假设我们有一个名为nums的数字列表，我们必须找到最长算术子序列的长度。我们知道，当S[i+1] – S[i]对于范围内的每个i（0 ≤ i < S大小- 1）具有相同的值时，序列S[i]是等差数列。

因此，如果输入是nums = [1, 4, 7, 10, 13, 20, 16]，那么输出将是6，子序列[1, 4, 7, 10 , 13, 16]是算术序列，因为每个相邻元素之间的差为3。

为了解决这个问题，我们将遵循以下步骤:

n := arr的大小
如果n <= 1，则
- 返回n
res := 0
dp :=空映射，默认情况下，当未找到key时，它将存储1
for i在范围1到n – 1中，执行
- for j在范围0到i – 1中执行
  - diff := arr[i] – arr[j]
  - dp[i，diff] := dp[j，diff] + 1
  - res := res和dp[I，diff之间的最大值
返回res

更多Python相关文章，请阅读：Python 教程

示例（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))