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

假设我们有一个名为 nums 的数字列表，我们需要找到最长算术子序列的长度。我们知道，当 S[i+1] - S[i] 对范围 (0 ≤ i < S 的大小 - 1) 中的每个 i 都有相同的值时，序列 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 := 一个空的映射，默认情况下，当找不到键时，它将存储 1
• 对于从 1 到 n - 1 的范围内的 i，执行以下操作：
  • 对于从 0 到 i - 1 的范围内的 j，执行以下操作：
    • diff := arr[i] - arr[j]
    • dp[i, diff] := dp[j, diff] + 1
    • res := res 和 dp[i, diff 的最大值
• 返回 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

Arnab Chakraborty

更新于： 2020年12月12日

324 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习