โปรแกรมหาทางลาดความกว้างสูงสุดใน Python

สมมติว่าเรามีจำนวนอาร์เรย์ ทางลาดคือทูเพิล (i, j) ซึ่ง i

ดังนั้น หากอินพุตเท่ากับ nums =[6,0,8,2,1,5] เอาต์พุตจะเป็น 4 เนื่องจากความลาดของความกว้างสูงสุดอยู่ที่ (i, j) =(1, 5) และ nums [1] =0 และ nums[5] =5.

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

• B :=แผนที่ใหม่

• สำหรับฉันในช่วง 0 ถึงขนาดของ nums ทำ

  • x :=nums[i]

  • ถ้า x อยู่ใน B แล้ว

    • ใส่ i ต่อท้าย B[x]

  • มิฉะนั้น

    • B[x] :=[i]

• mini :=รายการเริ่มต้นเก็บหนึ่ง inf ลงในนั้น

• maxi :=รายการเริ่มต้นเก็บหนึ่ง -inf ลงในนั้น

• สำหรับแต่ละ x ในการเรียงลำดับรายการของคีย์ทั้งหมดของ B ทำ

  • ใส่ขั้นต่ำขององค์ประกอบสุดท้ายของ mini และขั้นต่ำของ B[x] ที่ส่วนท้ายของ mini

• สำหรับแต่ละ x ในรายการเรียงลำดับกลับกันของคีย์ทั้งหมดของ B ให้ทำ

  • ใส่ขั้นต่ำขององค์ประกอบสุดท้ายของ mini และขั้นต่ำของ B[x] ที่ส่วนท้ายของ mini

• maxi :=ย้อนกลับ maxi จากนั้นนำ subarray จากจุดเริ่มต้นไปยังองค์ประกอบสุดท้ายที่สอง

• mini :=subarray ของ mini[จากดัชนี 1 ถึงปลาย]

• p :=0

• res :=-inf

• ในขณะที่ p <ขนาดของมินิ ทำ

  • res :=สูงสุดของ res และ (maxi[p] - mini[p])

  • p :=p + 1

• ผลตอบแทน

ตัวอย่าง

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

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

อินพุต

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

ผลลัพธ์

4