ได้รับลิสต์จำนวนบวก ลบ sublist ติดกันที่มีค่าเท่ากัน ความยาว t ได้คะแนน t² ทำซ้ำจนลิสต์ว่าง หา คะแนนสูงสุด
ตัวอย่าง
Input: [4, 4, 6, 4, 4]
Output: 17
ลบ 6 (t=1) → 1 แล้วเหลือ [4,4,4,4] (t=4) → 16 รวม 17
แนวทางแก้ปัญหา
Interval DP (DP on intervals):
- State:
dp(l, r, k)= คะแนนสูงสุดในช่วง[l, r]โดยมีkตัวเท่ากับnums[l]ต่ออยู่ด้านซ้าย (outside) - Base:
l > r→ 0 - Merge ตัวเดียวกันติดกัน: ขยาย
lไปขวา รวมk - สองทางเลือก:
- ลบกลุ่มนี้เลย:
(k+cnt)² + dp(l+cnt, r, 0) - หาตัวกลางที่เท่ากัน merge ต่อ:
max(dp(l+cnt, m-1, 0) + dp(m, r, k+cnt))
- ลบกลุ่มนี้เลย:
การใช้งาน (Python)
from functools import lru_cache
class Solution:
def solve(self, nums):
@lru_cache(None)
def dp(l, r, k):
if l > r:
return 0
# รวมตัวติดกันที่เท่ากับ nums[l]
val = nums[l]
l2 = l
while l2 < r and nums[l2 + 1] == val:
l2 += 1
cnt = l2 - l + 1
new_l = l2 + 1
new_k = k + cnt
# Option 1: ลบกลุ่มนี้ตอนนี้
best = new_k * new_k + dp(new_l, r, 0)
# Option 2: หาตัวกลาง merge ต่อ
for m in range(new_l, r + 1):
if nums[m] == val:
best = max(best, dp(new_l, m - 1, 0) + dp(m, r, new_k))
return best
return dp(0, len(nums) - 1, 0)
# ทดสอบ
ob = Solution()
print(ob.solve([4, 4, 6, 4, 4])) # Output: 17
ความซับซ้อน
- Time Complexity: O(N³) หรือ O(N⁴) ขึ้นกับการ implement
- Space Complexity: O(N³) สำหรับ memo
เป็นปัญหา "Remove Boxes" (LeetCode 546) รุ่นง่ายขึ้น
