โปรแกรมหาขนาด subsequence สูงสุดที่ทุกคู่เป็นคู่ที่ดีใน Python

ได้รับลำดับ nums ต้องการหาขนาดของ subsequence ที่ใหญ่ที่สุดซึ่งทุกคู่ (p,q) ใน subsequence เป็น "คู่ที่ดี" โดยคู่ที่ดีหมายถึงตรงตามเงื่อนไขอย่างน้อยหนึ่งข้อ: 1. ความคี่หรือคู่ของจำนวนเฉพาะที่แตกต่างกันของ p และ q เท่ากัน 2. ความคี่หรือคู่ของผลรวมตัวหารของ p และ q เท่ากัน

ตัวอย่าง: nums = [2,3,6,8] ผลลัพธ์คือ 3

ขั้นตอนการแก้ปัญหา

1. สำหรับแต่ละตัวเลขใน nums คำนวณ:
   • จำนวนเฉพาะที่แตกต่างกัน (นับ parity)
   • ผลรวมตัวหารทั้งหมด (นับ parity)
2. จัดกลุ่มตัวเลขตาม parity ทั้งสองอย่าง
3. หาขนาดกลุ่มที่ใหญ่ที่สุดที่ทุกคู่ในกลุ่มมี parity เหมือนกันในอย่างน้อยหนึ่งคุณสมบัติ

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

def solve(nums):
    n = len(nums)
    cnt = []   # parity ของจำนวนเฉพาะที่แตกต่างกัน
    total = [] # parity ของผลรวมตัวหาร
    for i in nums:
        # นับเฉพาะที่แตกต่างกัน
        count = 0
        for j in range(2, i + 1):
            if all(j % k != 0 for k in range(2, int(j**0.5)+1)):
                if i % j == 0:
                    count += 1
        cnt.append('even' if count % 2 == 0 else 'odd')
        # ผลรวมตัวหาร
        tot = 0
        for j in range(1, i + 1):
            if i % j == 0:
                tot += j
        total.append('even' if tot % 2 == 0 else 'odd')
    # หา subsequence ใหญ่ที่สุดที่ทุกคู่ตรงเงื่อนไข
    # เนื่องจากเงื่อนไขเป็น equivalence relation เราสามารถจัดกลุ่มได้
    from collections import defaultdict
    groups = defaultdict(list)
    for idx, (c, t) in enumerate(zip(cnt, total)):
        groups[(c, t)].append(nums[idx])
    max_size = max(len(g) for g in groups.values())
    return max_size

# ทดสอบ
nums = [2, 3, 6, 8]
print(solve(nums))  # ผลลัพธ์: 3

อินพุตตัวอย่าง

15, 3, 8

เอาต์พุตตัวอย่าง

3