Tìm điểm tối đa bằng cách xóa phần tử từ mảng trong Python

Cho mảng A N phần tử, và hai số l, r (1 ≤ a[x] ≤ 10⁵, 1 ≤ l ≤ r ≤ N). Lấy phần tử a[x] xóa nó, đồng thời xóa tất cả phần tử bằng a[x]+1...a[x]+r và a[x]-1...a[x]-l. Chi phí = a[x] điểm. Tối đa hóa tổng chi phí sau khi xóa hết mảng.

Ví dụ: A = [2,4,3,10,5], l = 1, r = 2 → Kết quả: 18.

Thuật toán Dynamic Programming

1. Tìm max_val = max(A).
2. count_list[v] = tần suất giá trị v trong A.
3. res[v] = điểm tối đa cho các giá trị ≤ v.
4. Quy hoạch: res[num] = max(res[num-1], num * count_list[num] + res[max(num - l - 1, 0)]).
5. Trả về res[max_val].

Ví dụ code

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

array = [2, 4, 3, 10, 5]
left = 1
right = 2
print(get_max_cost(array, left, right))

Input

[2, 4, 3, 10, 5], 1, 2

Output

18