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

在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))

输入

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

输出

6

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程