โปรแกรมค้นหาลำดับย่อยที่ยาวที่สุดโดยที่ความแตกต่างแน่นอนระหว่างทุกองค์ประกอบที่อยู่ติดกันมากที่สุด k ใน Python

สมมติว่าเราได้รับรายการตัวเลขและค่าอื่น k คราวนี้งานของเราคือการหาความยาวของลำดับย่อยที่ยาวที่สุดโดยที่ความแตกต่างที่แน่นอนระหว่างองค์ประกอบที่อยู่ติดกันทุกตัวมีค่าสูงสุด k

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[5, 6, 2, 1, −6, 0, -1, k =4 ผลลัพธ์จะเป็น 6

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

• กำหนดฟังก์ชั่น update() นี่จะใช้เวลา i, x

• ผม :=ผม + n

• ในขณะที่ฉันไม่เป็นศูนย์ ให้ทำ

  • segtree[i] :=สูงสุดของ segtree[i], x

  • ผม :=ผม / 2

• กำหนดฟังก์ชั่น query() นี่จะใช้เวลา i, j

• ตอบ :=−อนันต์

• ผม :=ผม + n

• j :=j + n + 1

• ในขณะที่ i

  • ถ้าฉัน mod 2 เหมือนกับ 1 แล้ว

    • ans :=สูงสุดของ ans, segtree[i]

    • ผม :=ผม + 1

  • ถ้า j mod 2 เหมือนกับ 1 แล้ว

    • j :=j − 1

    • ans :=สูงสุดของ ans, segtree[j]

  • ผม :=ผม / 2

  • เจ :=เจ / 2

• กลับมาอีกครั้ง

• ในหน้าที่หลัก ให้ทำดังต่อไปนี้ −

• nums =[5, 6, 2, 1, −6, 0, −1]

• k =4

• n =2 ยกกำลัง (ฐานลอการิทึม 2 ของ (ความยาวของ (ตัวเลข) + 1) + 1)

• segtree :=[0] * 100000

• snums :=เรียงลำดับรายการ nums

• index :=สร้างคอลเลกชันโดยที่ x:i สำหรับแต่ละดัชนี i และองค์ประกอบ x ใน (snums)

• ตอบ :=0

• สำหรับแต่ละ x เป็นตัวเลข ทำ

  • แท้จริง :=ส่งคืนตำแหน่งซ้ายสุดจาก snums โดยที่ (x − k) สามารถแทรกได้ในขณะที่รักษาลำดับที่จัดเรียงไว้

  • สวัสดี :=(ตำแหน่งซ้ายสุดจาก snums โดยที่ (x + k) สามารถแทรกได้ในขณะที่ยังคงเรียงลำดับ) − 1

  • นับ :=แบบสอบถาม (สวัสดี)

  • อัปเดต (ดัชนี[x], นับ + 1)

  • ans :=สูงสุดของ ans นับ + 1

• กลับมาอีกครั้ง

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

ตัวอย่าง

import math, bisect
class Solution:
   def solve(self, nums, k):
      n = 2 ** int(math.log2(len(nums) + 1) + 1)
      segtree = [0] * 100000
      def update(i, x):
         i += n
         while i:
            segtree[i] = max(segtree[i], x)
            i //= 2
         def query(i, j):
            ans = −float("inf")
            i += n
            j += n + 1
            while i < j:
               if i % 2 == 1:
                  ans = max(ans, segtree[i])
                  i += 1
               if j % 2 == 1:
                  j −= 1
                  ans = max(ans, segtree[j])
               i //= 2
               j //= 2
            return ans
         snums = sorted(nums)
         index = {x: i for i, x in enumerate(snums)}
         ans = 0
         for x in nums:
            lo = bisect.bisect_left(snums, x − k)
            hi = bisect.bisect_right(snums, x + k) − 1
            count = query(lo, hi)
            update(index[x], count + 1)
            ans = max(ans, count + 1)
      return ans
ob = Solution()
print(ob.solve([5, 6, 2, 1, −6, 0, −1], 4))

อินพุต

[5, 6, 2, 1, −6, 0, −1], 4

ผลลัพธ์

6