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

Cho mảng nums (chỉ giá trị dương), muốn xóa một mảng con chứa các phần tử duy nhất. Điểm = tổng mảng con. Tìm điểm tối đa bằng cách xóa đúng một mảng con.

Ví dụ: nums = [6,3,2,3,6,3,2,3,6], đầu ra = 11 (mảng con tối ưu [6,3,2] hoặc [2,3,6]).

Giải pháp

Sliding window tìm mảng con phần tử duy nhất có tổng lớn nhất:

• seen := map mới, ans := sum := 0, l := 0
• Với mỗi index r, value x trong nums:
  • Nếu x trong seen:
    • index := seen[x]
    • Khi l <= index: xóa seen[nums[l]], sum -= nums[l], l += 1
  • seen[x] := r, sum += x, ans := max(ans, sum)
• Trả về ans

Ví dụ minh họa

Xem 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