Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

Python में सबसे लंबे सर्कुलर बढ़ते सबसीक्वेंस की लंबाई खोजने का प्रोग्राम


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

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

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

  • a := nums के आकार से दोगुनी आकार की सूची बनाएं और nums को दो बार भरें
  • ans := 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 के आकार का अधिकतम
  • ans लौटाएं

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

उदाहरण

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
  1. - पायथन में सबसे लंबे लगातार अनुक्रम की लंबाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक असॉर्टेड सरणी है, हमें लगातार तत्वों के सबसे लंबे अनुक्रम की लंबाई ढूंढनी है। उदाहरण के लिए, यदि इनपुट nums = [70, 7, 50, 4, 6, 5] है, तो आउटपुट 4 होगा, क्योंकि सबसे लंबा लगातार अनुक्रम [4, 5, 6, 7] है, इसलिए हम इसकी लंबाई 4 लौटाते हैं। इसे हल करने के लिए हम निम्न चरणों का पाल

  1. - पायथन में सबसे लंबी एनाग्राम उप-अनुक्रम की लंबाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास दो लोअरकेस स्ट्रिंग्स S और T हैं, हमें सबसे लंबी एनाग्राम उप-अनुक्रम की लंबाई ढूंढनी है। उदाहरण के लिए, यदि इनपुट S = helloworld, T = hellorld है, तो आउटपुट 8 होगा। इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे: c := एक नया मैप, d := एक नया मैप। i को 0 से len(a) - 1 तक लूप म

  1. - पायथन में सबसे लंबे संतुलित उप-अनुक्रम की लंबाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक स्ट्रिंग s है जिसमें ब्रैकेट्स ( और ) हैं, हमें संतुलित ब्रैकेट्स के सबसे लंबे उप-अनुक्रम की लंबाई ढूंढनी है। उदाहरण के लिए, यदि इनपुट s = ())(()( है, तो आउटपुट 4 होगा, क्योंकि हम ()() जैसा उप-अनुक्रम ले सकते हैं। इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे: res := 0, n