หาคะแนนสูงสุดจากการลบอิลิเมนต์ในอาร์เรย์ (Python)

โจทย์: กำหนดอาร์เรย์ A, ตัวเลข l, r เลือก ax ลบออก ได้คะแนน ax พร้อมลบ ax+1...ax+r และ ax-1...ax-l ด้วย หาคะแนนรวมสูงสุด

ตัวอย่าง: A=[2,4,3,10,5], l=1, r=2 → output=18

อัลกอริทึม Dynamic Programming

คล้ายปัญหา "Delete and Earn" / "House Robber" แปลงเป็นปัญหาเลือกตัวเลขไม่ติดกัน

1. นับความถี่แต่ละค่า (count_list)
2. DP[num] = max(DP[num-1], num × count[num] + DP[num-l-1])
3. คำตอบ = DP[max_val]

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

def get_max_cost(array, left, right):
    n = len(array)
    max_val = max(array)
    count_list = [0] * (max_val + 1)
    for val in array:
        count_list[val] += 1
    
    dp = [0] * (max_val + 1)
    left = min(left, right)
    
    for num in range(1, max_val + 1):
        k = max(num - left - 1, 0)
        dp[num] = max(dp[num-1], num * count_list[num] + dp[k])
    
    return dp[max_val]

print(get_max_cost([2,4,3,10,5], 1, 2))  # 18

ผลลัพธ์

18

สรุป: แปลงปัญหาเป็น DP บนค่าตัวเลข (ไม่ใช่ index) ใช้หลักการว่าเลือกค่า x ก็ต้องไม่เลือกช่วง [x-l, x+r] เหมือน House Robber แบบขยายช่วง