ค้นหาคะแนนสูงสุดที่สามารถรับได้โดยการลบองค์ประกอบออกจากอาร์เรย์ใน Python

สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ N เราก็มีเลขจำนวนเต็มสองจำนวน l และ r โดยที่ 1≤ ax ≤ 10^5 และ 1≤ l≤ r≤ N รับองค์ประกอบ จากอาร์เรย์ว่า axe และลบออก และลบองค์ประกอบทั้งหมดเท่ากับ 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 ทำ
- count_list[array[i]] :=count_list[array[i]] + 1
res :=ขนาดอาร์เรย์ (max_val + 1) เติม 0
res[0] :=0
ซ้าย :=ต่ำสุด ซ้าย ขวา
สำหรับ num ในช่วง 1 ถึง max_val + 1 ทำ
- k :=สูงสุด num - ซ้าย - 1, 0
- res[num] :=สูงสุดของ res[num - 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