पायथन में दी गई सूची से सबसे लंबे समय तक वैकल्पिक अनुक्रम की लंबाई खोजने का कार्यक्रम

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

इसलिए, यदि इनपुट अंकों की तरह है =[6, 10, 4, 2, 3, 9, 4, 7], तो आउटपुट 6 होगा, जैसा कि आवश्यक बाद में है [6, 10, 2, 9, 4] , 7] और अंतर [4, -8, 7, -5, 3] हैं।

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

• n :=अंकों का आकार
• dp :=2n आकार की सूची और 1 से भरें
• उत्तर:=0
• मैं के लिए 0 से n की सीमा में, करते हैं
  • जे के लिए 0 से i की सीमा में, करें
    • यदि अंक[j] <अंक[i], तो
      • dp[i, 0] =अधिकतम dp[i, 0] और (dp[j, 1] + 1)
    • अन्यथा जब nums[j]> nums[i], तब
      • dp[i, 1] =अधिकतम dp[i, 1] और (dp[j, 0] + 1)
  • Ans =अधिकतम उत्तर, dp[i, 0] और dp[i, 1])
• वापसी उत्तर

उदाहरण (पायथन)

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

class Solution:
   def solve(self, nums):
      n = len(nums)
      dp = [[1] * 2 for _ in range(n)]
      ans = 0
      for i in range(n):
         for j in range(i):
            if nums[j] < nums[i]:
               dp[i][0] = max(dp[i][0], dp[j][1] + 1)
            elif nums[j] > nums[i]:
               dp[i][1] = max(dp[i][1], dp[j][0] + 1)
         ans = max(ans, dp[i][0], dp[i][1])
      return ans
ob = Solution()
nums = [6, 10, 4, 2, 3, 9, 4, 7]
print(ob.solve(nums))

इनपुट

[6, 10, 4, 2, 3, 9, 4, 7]

आउटपुट

6