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

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

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

วิธีแก้ปัญหา

• seen := แมปใหม่
• ans := sum := 0
• l := 0
• สำหรับแต่ละดัชนี r และค่า x ใน nums:
  • ถ้า x อยู่ใน seen:
    • index := seen[x]
    • while l <= index:
      • ลบ seen[nums[l]]
      • sum := sum - nums[l]
      • l := l + 1
  • seen[x] := r
  • sum := sum + x
  • ans := max(ans, sum)
• return ans

ตัวอย่าง

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