पायथन में सन्निहित कड़ाई से बढ़ती उपसूची की लंबाई खोजने का कार्यक्रम

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

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

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

• n :=अंकों का आकार

• पूर्व :=आकार n की सूची और 1s से भरें

• 1 से n-1 की श्रेणी में i के लिए, करें

  • अगर अंक [i]> अंक [i - 1], तो

    • पूर्व[i] :=पूर्व[i - 1] + 1

• suff :=आकार n की एक सूची और 1s से भरें

• n - 2 से -1 की श्रेणी में i के लिए, 1 से घटाएं, करें

  • अगर अंक [i] <अंक [i + 1], तो

    • suff[i] :=suff[i + 1] + 1

• उत्तर:=अधिकतम पूर्व और अधिकतम प्रत्यय का अधिकतम मूल्य

• 1 से n-1 की श्रेणी में i के लिए, करें

  • अगर अंक [i - 1] <अंक [i + 1], तो

    • उत्तर:=अधिकतम उत्तर और (पूर्व[i - 1] + प्रत्यय [i + 1])

• वापसी उत्तर

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

उदाहरण

class Solution:
   def solve(self, nums):
      n = len(nums)
      pre = [1] * n
      for i in range(1, n - 1):
         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