โปรแกรมหาความยาวของลำดับการเพิ่มขึ้นแบบวงกลมที่ยาวที่สุดใน python

สมมติว่าเรามีรายการของตัวเลขที่เรียกว่า nums เราต้องหาความยาวของลำดับย่อยที่เพิ่มขึ้นที่ยาวที่สุด และเราถือว่าหมายเลขลำดับถัดมาสามารถล้อมรอบจุดเริ่มต้นของรายการได้

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[6, 5, 8, 2, 3, 4] ผลลัพธ์จะเป็น 5 เนื่องจากลำดับการเพิ่มขึ้นที่ยาวที่สุดคือ [2, 3, 4, 6, 8]

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

• a :=ทำรายการขนาดสองครั้งของ nums และเติม nums สองครั้ง
• ตอบ :=0
• สำหรับ i ในช่วง 0 ถึงขนาดของ nums ให้ทำ
  • dp :=รายการใหม่
  • สำหรับ j ในช่วง i ถึงขนาดของ nums + i - 1 ทำ
    • n :=a[j]
    • k :=ออกจากดัชนีส่วนใหญ่เพื่อแทรก n ลงใน dp
    • ถ้า k เท่ากับขนาดของ dp แล้ว
      • ใส่ n ต่อท้าย dp
    • มิฉะนั้น
      • dp[k] :=n
    • ans :=สูงสุดของ ans และขนาด dp
• คืนสินค้า

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

ตัวอย่าง

import bisect
class Solution:
   def solve(self, nums):
      a = nums + nums
      ans = 0
      for i in range(len(nums)):
         dp = []
         for j in range(i, len(nums) + i):
            n = a[j]
            k = bisect.bisect_left(dp, n)
            if k == len(dp):
               dp.append(n)
            else:
               dp[k] = n
         ans = max(ans, len(dp))
      return ans

ob = Solution()
nums = [4, 5, 8, 2, 3, 4]
print(ob.solve(nums))

อินพุต

[4, 5, 8, 2, 3, 4]

ผลลัพธ์

5