โปรแกรมหาความยาวของลำดับย่อยเลขคณิตที่ยาวที่สุดใน Python

สมมติว่าเรามีรายการตัวเลขชื่อ nums เราต้องการหาความยาวของลำดับย่อยเลขคณิต (arithmetic subsequence) ที่ยาวที่สุด ลำดับเลขคณิตคือลำดับที่ความต่างระหว่างสมาชิกติดกันคงที่

เช่น ถ้าข้อมูลนำเข้าคือ nums = [1, 4, 7, 10, 13, 20, 16] ผลลัพธ์จะเป็น 6 เนื่องจากลำดับย่อย [1, 4, 7, 10, 13, 16] เป็นเลขคณิตที่ความต่าง 3

ขั้นตอนการแก้ปัญหา (DP + Hash Map)

• n := len(arr), ถ้า n <= 1 คืน n
• res := 0
• dp := defaultdict(lambda: 1) เก็บความยาวลำดับที่ลงท้ายที่ index i ด้วยความต่าง diff
• วน i = 1..n-1:
  • วน j = 0..i-1:
    • diff := arr[i] - arr[j]
    • dp[i, diff] = dp[j, diff] + 1
    • res = max(res, dp[i, diff])
• คืน res

ตัวอย่างโค้ด

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