Chương trình tìm giá trị tẩy tối đa trong Python

Giả sử chúng ta có một mảng gọi là nums (chỉ với các giá trị dương) và chúng ta muốn xóa một mảng con chứa các phần tử duy nhất. Chúng ta sẽ nhận được điểm là tổng các phần tử của mảng con. Chúng tôi phải tìm điểm tối đa có thể nhận được bằng cách xóa chính xác một mảng con.

Vì vậy, nếu đầu vào giống như nums =[6,3,2,3,6,3,2,3,6], thì đầu ra sẽ là 11, bởi vì ở đây mảng con tối ưu là [6,3,2] hoặc [2,3,6], vì vậy tổng là 11.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• đã thấy:=một bản đồ mới
• ans:=sum:=0
• l:=0
• đối với mỗi chỉ số r và giá trị x nums, thực hiện
  • nếu x xuất hiện trong đã thấy, thì
    • index:=saw [x]
    • while l <=index, do
      • xóa [nums [l]] đã nhìn thấy
      • sum:=sum - nums [l]
      • l:=l + 1
  • đã thấy [x]:=r
  • sum:=sum + x
  • ans:=tối đa của ans và tổng
• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

11