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

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


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

उदाहरण के लिए, यदि इनपुट nums = [30, 11, 12, 13, 14, 15, 18, 17, 32] है, तो आउटपुट 7 होगा, क्योंकि जब हम सूची में 18 को हटाते हैं तो हमें [11, 12, 13, 14, 15, 17, 32] मिलता है जो सबसे लंबी, सन्निकट, सख्ती से बढ़ती सबलिस्ट है, और इसकी लंबाई 7 है।

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

  • n := nums का आकार
  • pre := आकार n की सूची, 1 से भरी हुई
  • i को 1 से n-1 तक के लिए करें:
    • यदि nums[i] > nums[i-1], तो pre[i] := pre[i-1] + 1
  • suff := आकार n की सूची, 1 से भरी हुई
  • i को n-2 से -1 तक घटाते हुए करें:
    • यदि nums[i] < nums[i+1], तो suff[i] := suff[i+1] + 1
  • ans := max(pre का अधिकतम, suff का अधिकतम)
  • i को 1 से n-1 तक के लिए करें:
    • यदि nums[i-1] < nums[i+1], तो ans := max(ans, pre[i-1] + suff[i+1])
  • ans वापस करें

उदाहरण

class Solution:
    def solve(self, nums):
        n = len(nums)
        pre = [1] * n
        for i in range(1, n):
            if nums[i] > nums[i-1]:
                pre[i] = pre[i-1] + 1
        suff = [1] * n
        for i in range(n-2, -1, -1):
            if nums[i] < nums[i+1]:
                suff[i] = suff[i+1] + 1
        ans = max(max(pre), max(suff))
        for i in range(1, n-1):
            if nums[i-1] < nums[i+1]:
                ans = max(ans, pre[i-1] + suff[i+1])
        return ans
ob = Solution()
nums = [30, 11, 12, 13, 14, 15, 18, 17, 32]
print(ob.solve(nums))

इनपुट

[30, 11, 12, 13, 14, 15, 18, 17, 32]

आउटपुट

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

    मान लीजिए हमारे पास संख्याओं की एक सूची है। हमें सबसे लंबी बढ़ती हुई उप-अनुक्रम (Longest Increasing Subsequence) की लंबाई ढूंढनी है। उदाहरण के लिए, यदि इनपुट [6, 1, 7, 2, 8, 3, 4, 5] है, तो आउटपुट 5 होगा, क्योंकि सबसे लंबी बढ़ती हुई उप-अनुक्रम [2, 3, 4, 5, 6] है। इसे हल करने के लिए हम निम्न चरणों का

  1. - पायथन में सबसे लंबी विशिष्ट सबलिस्ट की लंबाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है, और हमें सबसे लंबी सन्निकट सबलिस्ट की लंबाई ढूंढनी है जहां सभी तत्व अद्वितीय हों। उदाहरण के लिए, यदि इनपुट nums = [6, 2, 4, 6, 3, 4, 5, 2] है, तो आउटपुट 5 होगा, क्योंकि अद्वितीय तत्वों की सबसे लंबी सूची [6, 3, 4, 5, 2] है। इसे हल करने के लिए हम नि

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

    मान लीजिए हमारे पास एक सरणी A है। हमें वह सन्निकट सबलिस्ट ढूंढनी है जिसका अधिकतम योग हो, और उसका योग भी लौटाना है। उदाहरण के लिए, यदि A = [-2,1,-3,4,-1,2,1,-5,4], तो योग 6 होगा। और सबअरे [4, -1, 2, 1] होगा। इसे हल करने के लिए हम डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे। dp सरणी A के आकार की