Chương trình tìm độ dài của dãy con tăng dần hình tròn dài nhất trong python

Giả sử chúng ta có một danh sách các số được gọi là num, chúng ta phải tìm độ dài của dãy con dài nhất tăng dần và chúng ta giả sử dãy con có thể quấn quanh đầu danh sách.

Vì vậy, nếu đầu vào giống như nums =[6, 5, 8, 2, 3, 4], thì đầu ra sẽ là 5, vì dãy con tăng dài nhất là [2, 3, 4, 6, 8].

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

• a:=tạo danh sách có kích thước gấp đôi số num và điền hai lần số num
• ans:=0
• đối với tôi trong phạm vi từ 0 đến kích thước là num, hãy thực hiện
  • dp:=một danh sách mới
  • đối với j trong phạm vi i đến kích thước của nums + i - 1, thực hiện
    • n:=a [j]
    • k:=chỉ mục ngoài cùng bên trái để chèn n vào dp
    • nếu k giống với kích thước của dp, thì
      • chèn n vào cuối dp
    • nếu không,
      • dp [k]:=n
    • ans:=tối đa là ans và kích thước là dp
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

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

Đầu ra

5