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

สมมติว่าเรามีรายการตัวเลข nums และค่าอื่นที่ต่างออกไป เราต้องหาความยาวของลำดับย่อยของเลขคณิตที่ยาวที่สุด โดยที่ผลต่างระหว่างจำนวนที่ต่อเนื่องกันในลำดับย่อยจะเหมือนกับค่า diff

ดังนั้น หากอินพุตเป็น nums =[-1, 1, 4, 7, 2, 10] diff =3 ผลลัพธ์จะเป็น 4 เพราะเราสามารถเลือกลำดับย่อยได้เช่น [1, 4, 7, 10 ].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• เห็น :=พจนานุกรมว่างเปล่า ค่าเริ่มต้นคือ 0 เมื่อไม่มีคีย์
• mx :=0
• สำหรับแต่ละ x เป็น nums ทำ
  • ถ้าเห็น x - diff แล้ว
    • เห็น[x] :=เห็น[x - diff] + 1
  • มิฉะนั้น
    • เห็น[x] :=1
  • mx :=สูงสุดของ mx และเห็น[x]
• ผลตอบแทน mx

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

from collections import defaultdict
def solve(nums, diff):
   seen = defaultdict(int)
   mx = 0
   for x in nums:
      if x - diff in seen:
         seen[x] = seen[x - diff] + 1
      else:
         seen[x] = 1
      mx = max(mx, seen[x])
   return mx

nums = [-1, 1, 4, 7, 2, 10]
diff = 3
print(solve(nums, diff))

อินพุต

[-1, 1, 4, 7, 2, 10], 3

ผลลัพธ์

4