Giả sử chúng ta có một mảng A với N phần tử, chúng ta cũng có hai số nguyên l và r trong đó, 1≤ ax ≤ 10 ^ 5 và 1≤ l≤ r≤ N. Lấy một phần tử khỏi mảng nói ax và loại bỏ nó, đồng thời loại bỏ tất cả các phần tử bằng ax + 1, ax + 2… ax + R và ax-1, ax-2… ax-L khỏi mảng đó. Bằng cách này, nó sẽ mất điểm rìu. Chúng tôi phải tối đa hóa tổng chi phí sau khi xóa tất cả các phần tử khỏi mảng.
Vì vậy, nếu đầu vào là A =[2,4,3,10,5], l =1, r =2, thì đầu ra sẽ là 18.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
n:=kích thước của mảng
-
max_val:=0
-
đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện
-
max_val:=tối đa của max_val, mảng [i]
-
-
count_list:=một mảng có kích thước (max_val + 1), điền bằng 0
-
đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện
-
count_list [array [i]]:=count_list [array [i]] + 1
-
-
res:=một mảng có kích thước (max_val + 1), điền bằng 0
-
res [0]:=0
-
left:=tối thiểu trái, phải
-
đối với num trong phạm vi 1 đến max_val + 1, hãy thực hiện
-
k:=tối đa num - left - 1, 0
-
res [num]:=tối đa res [num - 1], num * count_list [num] + res [k]
-
-
trả về res [max_val]
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def get_max_cost(array, left, right) : n = len(array) max_val = 0 for i in range(n) : max_val = max(max_val, array[i]) count_list = [0] * (max_val + 1) for i in range(n) : count_list[array[i]] += 1 res = [0] * (max_val + 1) res[0] = 0 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))
Đầu vào
[2,4,3,10,5] , 1, 2
Đầu ra
18