পাইথনের অ্যারে থেকে উপাদানগুলি মুছে ফেলার মাধ্যমে সর্বাধিক পয়েন্টগুলি সন্ধান করুন

ধরুন আমাদের কাছে N উপাদানগুলির সাথে একটি অ্যারে A আছে, আমাদের কাছে দুটি পূর্ণসংখ্যা l এবং r রয়েছে যেখানে, 1≤ ax ≤ 10^5 এবং 1≤ l≤ r≤ N। একটি উপাদান নেওয়া হচ্ছে অ্যারে থেকে ax বলুন এবং এটি সরিয়ে দিন এবং সেই অ্যারে থেকে ax+1, ax+2 … ax+R এবং ax-1, ax-2 … ax-L এর সমান সমস্ত উপাদান মুছে দিন। এতে করে কুঠার পয়েন্ট খরচ হবে। অ্যারে থেকে সমস্ত উপাদান মুছে ফেলার পরে আমাদের মোট খরচ সর্বাধিক করতে হবে।

সুতরাং, যদি ইনপুটটি A =[2,4,3,10,5], l =1, r =2 এর মত হয়, তাহলে আউটপুট হবে 18।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

n :=অ্যারের আকার
max_val :=0
0 থেকে n রেঞ্জের জন্য, করুন
- max_val :=max_val এর সর্বোচ্চ, অ্যারে[i]
count_list :=আকারের একটি অ্যারে (max_val + 1), 0 দিয়ে পূরণ করুন
0 থেকে n রেঞ্জের জন্য, করুন
- গণনা_তালিকা[অ্যারে[i]] :=গণনা_তালিকা[অ্যারে[i]] + 1
res :=আকারের একটি অ্যারে (max_val + 1), 0 দিয়ে পূরণ করুন
res[0] :=0
বাম :=সর্বনিম্ন বাম, ডান
রেঞ্জ 1 থেকে max_val + 1 এর সংখ্যার জন্য, করুন
- k :=সর্বাধিক সংখ্যা - বাম - 1, 0
- res[সংখ্যা] :=res এর সর্বাধিক [সংখ্যা - 1], num * count_list[num] + res[k]
রিটার্ন রিটার্ন [max_val]

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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))

ইনপুট

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