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 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習