पायथन में सबसे लंबे समय तक सर्कुलर बढ़ने के बाद की लंबाई खोजने का कार्यक्रम

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है, हमें सबसे लंबे समय तक बढ़ते क्रम की लंबाई का पता लगाना होगा और हम यह मान रहे हैं कि अनुवर्ती सूची की शुरुआत के आसपास लपेटा जा सकता है।

इसलिए, यदि इनपुट संख्या =[6, 5, 8, 2, 3, 4] की तरह है, तो आउटपुट 5 होगा, क्योंकि सबसे लंबे समय तक बढ़ने वाला क्रम [2, 3, 4, 6, 8] है। पी>

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• a :=दो बार अंकों के आकार की सूची बनाएं और अंकों को दो बार भरें
• उत्तर:=0
• मैं के लिए 0 से लेकर अंकों के आकार तक, करें
  • dp:=एक नई सूची
  • j के लिए i से लेकर अंकों के आकार के लिए + i-1, do
    • n :=a[j]
    • k :=n को dp में डालने के लिए सबसे अधिक इंडेक्स छोड़ दिया
    • यदि k, dp के आकार के समान है, तो
      • dp के अंत में n डालें
    • अन्यथा,
      • dp[k] :=n
    • उत्तर:=अधिकतम उत्तर और डीपी का आकार
• वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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