โปรแกรมหาค่าการลบสูงสุดใน Python

สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums (ที่มีค่าบวกเท่านั้น) และเราต้องการลบอาร์เรย์ย่อยที่มีองค์ประกอบเฉพาะ เราจะได้คะแนนที่เป็นผลรวมขององค์ประกอบย่อย เราต้องหาคะแนนสูงสุดที่ทำได้โดยลบอาร์เรย์ย่อยหนึ่งรายการ

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[6,3,2,3,6,3,2,3,6] เอาต์พุตจะเป็น 11 เพราะอาร์เรย์ย่อยที่เหมาะสมที่สุดคือ [6,3,2] หรือ [2,3,6] ผลรวมคือ 11

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• เห็น :=แผนที่ใหม่
• ตอบ :=ผลรวม :=0
• l :=0
• สำหรับแต่ละดัชนี r และค่า x nums ทำ
  • ถ้า x ปรากฏให้เห็นแล้ว
    • ดัชนี :=เห็น[x]
    • ในขณะที่ l <=ดัชนี ทำ
      • ลบ เห็น[nums[l]]
      • sum :=sum - nums[l]
      • l :=l + 1
  • เห็น[x] :=r
  • sum :=sum + x
  • ans :=สูงสุดของ ans และ sum
• คืนสินค้า

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(nums):
   seen = dict()
   ans = sum = 0
   l = 0
   for r, x in enumerate(nums):
      if x in seen:
         index = seen[x]
         while l <= index:
            del seen[nums[l]]
            sum -= nums[l]
            l += 1

      seen[x] = r
      sum += x
      ans = max(ans, sum)
   return ans

nums = [6,3,2,3,6,3,2,3,6]
print(solve(nums))

อินพุต

[6,3,2,3,6,3,2,3,6]

ผลลัพธ์

11