โปรแกรมค้นหาความยาวของรายการย่อยที่ยาวที่สุดใน Python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และเราต้องหาความยาวของรายการย่อยที่อยู่ติดกันที่ยาวที่สุด โดยที่องค์ประกอบทั้งหมดไม่ซ้ำกัน

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[6, 2, 4, 6, 3, 4, 5, 2] ผลลัพธ์จะเป็น 5 เนื่องจากรายการองค์ประกอบที่ไม่ซ้ำที่ยาวที่สุดคือ [6, 3, 4, 5 , 2].

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

• head :=0, dct :=แผนที่ใหม่

• max_dist :=0

• สำหรับแต่ละดัชนี i และองค์ประกอบ num เป็น num ให้ทำ

  • ถ้า num อยู่ใน dct และ dct[num]>=head แล้ว

    • หัว :=dct[num] + 1

  • dct[num] :=ฉัน

  • ถ้าฉัน - หัว + 1> max_dist แล้ว

    • max_dist :=i - หัว + 1

• ส่งคืน max_dist

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

ตัวอย่าง

class Solution:
   def solve(self, nums):
      head = 0
      dct = {}
      max_dist = 0
      for i, num in enumerate(nums):
         if num in dct and dct[num] >= head:
            head = dct[num] + 1
         dct[num] = i
         if i - head + 1 > max_dist:
            max_dist = i - head + 1
   return max_dist
ob = Solution()
nums = [6, 2, 4, 6, 3, 4, 5, 2]
print(ob.solve(nums))

อินพุต

[6, 2, 4, 6, 3, 4, 5, 2]

ผลลัพธ์

5