ข้อ 51 · LC2542 Maximum Subsequence Score (คะแนน subsequence มากสุด) 🟡

โจทย์ (LC2542): กำหนด array จำนวนเต็ม nums1 และ nums2 ที่ยาวเท่ากัน n ตัว พร้อมจำนวนเต็มบวก k ให้เลือก index มา k ตำแหน่งจาก nums1 (แบบ subsequence) โดยนิยาม score (คะแนน) ของชุดที่เลือกคือ ผลรวมของค่า nums1 ที่ตำแหน่งที่เลือก คูณด้วยค่า minimum ของ nums2 ที่ตำแหน่งเดียวกันที่เลือก ให้ return score ที่มากที่สุดที่เป็นไปได้

แนวทาง — ต้องใช้อะไร & คิดยังไง

โครงสร้างที่ใช้: sort (เรียง) + min-heap ความยากของโจทย์คือ score ขึ้นกับสองอย่างพร้อมกัน: sum nums1 (ยิ่งมากยิ่งดี) กับ min ของ nums2 (ยิ่งมากยิ่งดี) การ handle สองตัวแปรพร้อมกันยาก เทคนิคคือ ตรึง (fix) ตัวหนึ่งไว้ก่อน

คิดแบบง่าย/ช้าก่อน: ลองทุก subset (สับเซ็ต) ขนาด k แล้วคิด score เป็น O(C(n,k)) ซึ่งระเบิดทันที เราจึง sort คู่ (nums1, nums2) ตาม nums2 จากมากไปน้อย แล้ว iterate ไปทีละตัว เมื่อถึงคู่ที่ nums2 = b เราตั้งให้ b เป็นตัว minimum ของกลุ่ม แปลว่าเลือกได้เฉพาะตัวที่มาก่อนหน้า (nums2 ใหญ่กว่าหรือเท่ากับ b) เท่านั้น

1. จับคู่ zip(nums1, nums2) แล้ว sort ตาม nums2 จากมากไปน้อย
2. iterate ทีละคู่ (a, b): push a เข้า min-heap และบวก a เข้าตัวแปร total
3. ถ้า heap เกิน k ตัว ให้ pop ตัว nums1 ที่ minimum ออก พร้อมลบมันออกจาก total
4. เมื่อ heap ครบ k ตัวพอดี b ตัวปัจจุบันคือ min ของ nums2 ในกลุ่ม compute total * b แล้ว track ค่ามากสุดไว้ใน best

ไล่ทีละสเต็ป

จำลอง nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3 หลัง sort ตาม nums2 มากไปน้อยได้ pairs = [(2,4),(3,3),(1,2),(3,1)]:

best = max(12, 8) = 12

import heapq

def max_score(nums1, nums2, k):
    # จับคู่แล้วเรียงตาม nums2 จากมากไปน้อย
    pairs = sorted(zip(nums1, nums2), key=lambda p: -p[1])

    heap = []          # min-heap เก็บค่า nums1 ของตัวที่เลือกไว้
    total = 0          # ผลรวม nums1 ในกลุ่มที่เลือก
    best = 0
    for a, b in pairs:
        heapq.heappush(heap, a)
        total += a
        # ถ้าเลือกเกิน k ตัว ทิ้ง nums1 ที่น้อยสุดออก
        if len(heap) > k:
            total -= heapq.heappop(heap)
        # เมื่อครบ k ตัว: b ตัวปัจจุบันคือ min ของ nums2 ในกลุ่ม (เพราะเรียงลดหลั่น)
        if len(heap) == k:
            best = max(best, total * b)
    return best

print(max_score([1, 3, 3, 2], [2, 1, 3, 4], 3))  # 12
print(max_score([4, 2, 3, 1, 1], [7, 5, 10, 9, 6], 1))  # 30

12
30