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

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

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

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम डायनामिक प्रोग्रामिंग का उपयोग करेंगे जहां dp[i][0] i पर समाप्त होने वाले सबसीक्वेंस की लंबाई दर्शाता है जिसका अंतिम अंतर पॉजिटिव है, और dp[i][1] नेगेटिव अंतर के लिए:

• n := nums का आकार
• dp := आकार 2n की लिस्ट, 1 से भरी हुई
• ans := 0
• i को 0 से n-1 तक लूप चलाएं:
  • j को 0 से i-1 तक लूप चलाएं:
    • यदि nums[j] < nums[i] है, तो dp[i][0] = max(dp[i][0], dp[j][1] + 1)
    • अन्यथा यदि nums[j] > nums[i] है, तो dp[i][1] = max(dp[i][1], dp[j][0] + 1)
  • ans = max(ans, dp[i][0], dp[i][1])
• ans लौटाएं

पायथन कार्यान्वयन

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