Chương trình tìm điểm tối đa từ việc xóa dãy con liên tiếp cùng giá trị trong Python

Cho mảng số dương. Có thể xóa dãy con liên tiếp cùng giá trị độ dài t được t*t điểm. Lặp cho đến mảng rỗng. Tìm điểm tối đa.

Ví dụ: [4,4,6,4,4] → 17 (xóa 6 trước: 1đ, sau đó xóa 4 số 4: 16đ).

Giải thuật (DP đệ quy với nén nhóm liên tiếp)

Hàm dp(left, right, t): điểm max từ đoạn [left, right] với t phần tử cùng giá trị nums[left] đã gom từ bên trái.

• Nén nhóm liên tiếp đầu: left2 là cuối nhóm, t += left2-left+1, left = left2+1.
• Trường hợp 1: xóa nhóm này ngay → t^2 + dp(left, right, 0).
• Trường hợp 2: giữ lại, tìm mid sau cùng giá trị num, gom thêm: dp(left, mid-1, 0) + dp(mid, right, t).
• Lấy max.

Ví dụ minh họa

class Solution:
    def solve(self, nums):
        from functools import lru_cache
        
        @lru_cache(None)
        def dp(left, right, t):
            if left > right:
                return 0
            num = nums[left]
            left2 = left
            while left2 < right and nums[left2 + 1] == num:
                left2 += 1
            t += left2 - left + 1
            left = left2 + 1
            points = t * t + dp(left, right, 0)
            for mid in range(left, right + 1):
                if nums[mid] == num:
                    points = max(points, dp(left, mid - 1, 0) + dp(mid, right, t))
            return points
        
        return dp(0, len(nums) - 1, 0)

ob = Solution()
print(ob.solve([4, 4, 6, 4, 4]))  # Output: 17

Đầu vào / Đầu ra

Input: [4, 4, 6, 4, 4]

Output: 17