পাইথনে লিস্ট থেকে অল্টারনেটিং সাবসিকোয়েন্সের সর্বোচ্চ দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম

একটি সংখ্যা লিস্ট nums দেওয়া আছে। এমন একটি সাবসিকোয়েন্স খুঁজে বের করতে হবে যাতে সন্নিকট দুটি উপাদানের পার্থক্য (ডিফারেন্স) বारी-बারি থেকে পজিটিভ এবং নেগেটিভ হয় (অল্টারনেট করে)। প্রথম পার্থক্য পজিটিভ নাকি নেগেটিভ হতে পারে। সর্বোচ্চ দৈর্ঘ্য বের করতে হবে।

উদাহরণস্বরূপ, nums = [6, 10, 4, 2, 3, 9, 4, 7] হলে আউটপুট ৬। একটি সম্ভাব্য সাবসিকোয়েন্স: [6, 10, 2, 9, 4, 7] → পার্থক্য: [4, -8, 7, -5, 3]।

সমাধানের পদ্ধতি (DP)

1. n = len(nums)।
2. dp[i][0] = i-তম ইন্ডেক্সে শেষ হওয়া সাবসিকোয়েন্স যার শেষ পার্থক্য পজিটিভ, dp[i][1] = শেষ পার্থক্য নেগেটিভ। সব ১ দিয়ে ইনিশিয়ালাইজ।
3. ans = 0।
4. 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)।
5. ans = max(ans, dp[i][0], dp[i][1])।
6. 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