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

สมมติว่าเรามีรายการของตัวเลขที่เรียกว่า nums เราต้องหาความยาวของลำดับย่อยทางคณิตศาสตร์ที่ยาวที่สุด ดังที่เราทราบลำดับ S[i] เป็นลำดับเลขคณิตเมื่อ S[i+1] - S[i] มีค่าเท่ากันสำหรับทุก ๆ i ในช่วง (0 ≤ i <ขนาดของ S - 1)

ดังนั้น หากอินพุตเป็น 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 ทำ
  • สำหรับ j ในช่วง 0 ถึง i - 1 ทำ
    • diff :=arr[i] - arr[j]
    • dp[i, diff] :=dp[j, diff] + 1
    • res :=สูงสุดของ res และ dp[i, diff
• ผลตอบแทน

ตัวอย่าง (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