পাইথনে অ্যারে থেকে উপাদান ডিলিট করে সর্বোচ্চ পয়েন্ট বের করা

ধরা যাক একটি অ্যারে A আছে N উপাদানের সাথে, এবং দুটি ইন্টিজার l এবং r। অ্যারে থেকে একটি উপাদান ax নিলে সেটি এবং ax+1, ax+2...ax+r এবং ax-1, ax-2...ax-l এর সমান সব উপাদান রিমুভ হয়। এটি করতে ax পয়েন্ট খরচ হয়। সব উপাদান রিমুভ করার পর মোট পয়েন্ট সর্বাধিক করতে হবে।

যেমন, A=[2,4,3,10,5], l=1, r=2 হলে আউটপুট 18।

সমাধানের ধাপসমূহ

max_val := অ্যারের সর্বোচ্চ মান
count_list[max_val+1] তৈরি করুন এবং ফ্রিকোয়েন্সি গণনা করুন
res[max_val+1] DP অ্যারে তৈরি করুন
res[0] = 0, left = min(left, right)
for num in 1..max_val:
- k = max(num - left - 1, 0)
- res[num] = max(res[num-1], num * count_list[num] + res[k])
return res[max_val]

উদাহরণ

def get_max_cost(array, left, right):
    n = len(array)
    max_val = max(array)
    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))

ইনপুট

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