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

Cho danh sách số nums, tìm độ dài dãy con số học (arithmetic subsequence) dài nhất. Dãy số học là dãy mà hiệu giữa hai phần tử liên tiếp luôn bằng nhau.

Ví dụ: nums = [1, 4, 7, 10, 13, 20, 16] → dãy con [1, 4, 7, 10, 13, 16] có hiệu 3, độ dài 6.

Giải thuật (DP với từ điển hiệu)

• dp[(i, diff)] = độ dài dãy con số học kết thúc tại chỉ số i với công sai diff.
• Khởi tạo dp mặc định giá trị 1 (mỗi phần tử tự là dãy độ dài 1).
• Duyệt i từ 1 đến n-1, j từ 0 đến i-1:
  • diff = arr[i] - arr[j].
  • dp[(i, diff)] = dp[(j, diff)] + 1.
  • Cập nhật kết quả max.

Mã nguồn 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))  # Output: 6

Đầu vào

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

Đầu ra

6