Chương trình tìm độ dài của dãy con số học dài nhất của một danh sách nhất định bằng Python

Giả sử chúng ta có một danh sách các số được gọi là num, chúng ta phải tìm độ dài của dãy con số học dài nhất. Như chúng ta đã biết, dãy S [i] là dãy số học khi S [i + 1] - S [i] có cùng giá trị với mọi i trong phạm vi (0 ≤ i

Vì vậy, nếu đầu vào giống như nums =[1, 4, 7, 10, 13, 20, 16], thì đầu ra sẽ là 6, dãy con [1, 4, 7, 10, 13, 16] là một số học bởi vì sự khác biệt giữa mỗi phần tử liên tiếp là 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của arr
• nếu n <=1, thì
  • return n
• res:=0
• dp:=một bản đồ trống, theo mặc định, nó sẽ lưu trữ 1 bản đồ khi không tìm thấy khóa
• đối với tôi trong phạm vi từ 1 đến n - 1, thực hiện
  • đối với j trong phạm vi từ 0 đến i - 1, thực hiện
    • diff:=arr [i] - arr [j]
    • dp [i, diff]:=dp [j, diff] + 1
    • res:=tối đa res và dp [i, diff
• trả lại res

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

6