पायथन में सरणी से तत्वों को हटाकर प्राप्त किए जा सकने वाले अधिकतम अंक प्राप्त करें

मान लीजिए कि हमारे पास N तत्वों के साथ एक सरणी A है, हमारे पास दो पूर्णांक l और r भी हैं, जहां 1≤ ax 10^5 और 1≤ l≤ r≤ N. एक तत्व लेना सरणी से कुल्हाड़ी कहें और इसे हटा दें, और उस सरणी से 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, array[i]

• count_list :=आकार की एक सरणी (max_val + 1), 0 से भरें

• मेरे लिए 0 से n की सीमा में, करें

  • गिनती_सूची[सरणी[i]] :=count_list[सरणी[i]] + 1

• res :=आकार की एक सरणी (max_val + 1), 0 से भरें

• रेस [0] :=0

• बाएँ :=न्यूनतम बाएँ, दाएँ

• 1 से लेकर max_val + 1 तक की संख्या के लिए, करें

  • k :=अधिकतम संख्या - बायां - 1, 0

  • रेस [संख्या]:=अधिकतम रेस [संख्या -1], संख्या * गिनती_सूची [संख्या] + रेस [के]

• वापसी रेस [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

आउटपुट

18