Chương trình tìm đoạn đường nối có chiều rộng tối đa bằng Python

Giả sử chúng ta có một dãy nums, một đoạn đường nối là một bộ (i, j) mà i

Vì vậy, nếu đầu vào giống như nums =[6,0,8,2,1,5], thì đầu ra sẽ là 4 vì độ rộng tối đa đạt được tại (i, j) =(1,5) và nums [1] =0 và nums [5] =5.

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

• B:=một bản đồ mới

• đối với tôi trong phạm vi từ 0 đến kích thước của nums, hãy thực hiện

  • x:=nums [i]

  • nếu x nằm trong B thì

    • chèn i vào cuối B [x]

  • nếu không,

    • B [x]:=[i]

• mini:=một danh sách ban đầu lưu trữ một thông tin vào đó

• maxi:=một danh sách ban đầu lưu trữ một -inf vào đó

• cho mỗi x trong danh sách danh sách tất cả các khóa của B, làm

  • chèn tối thiểu phần tử cuối cùng của mini và tối thiểu B [x] vào cuối mini

• đối với mỗi x trong danh sách được sắp xếp lại của tất cả các khóa của B, thực hiện

  • chèn tối thiểu phần tử cuối cùng của mini và tối thiểu B [x] vào cuối mini

• maxi:=reverse maxi rồi lấy mảng con từ phần tử đầu tiên đến phần tử cuối cùng thứ hai

• mini:=subarray của mini [từ chỉ mục 1 đến cuối]

• p:=0

• res:=-inf

• while p

  • res:=tối đa của res và (maxi [p] - mini [p])

  • p:=p + 1

• trả lại res

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):
   B = {}
   for i in range(len(nums)):
      x = nums[i]
      if x in B:
         B[x].append(i)
      else:
         B[x] = [i]

   mini = [float('inf')]
   maxi = [float('-inf')]
   for x in sorted(B.keys()):
      mini.append(min(mini[-1], min(B[x])))

   for x in sorted(B.keys(), reverse = True):
      maxi.append(max(maxi[-1], max(B[x])))

   maxi = maxi[::-1][:-1]
   mini = mini[1:]

   p = 0
   res = float('-inf')
   while p < len(mini):
      res = max(res, maxi[p] - mini[p])
      p += 1

   return res

nums = [6,0,8,2,1,5]
print(solve(nums))

Đầu vào

[6,0,8,2,1,5]

Đầu ra

4