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

ধরুন আমাদের কাছে সংখ্যার একটি তালিকা আছে যাকে nums বলা হয়, আমাদেরকে দীর্ঘতম অনুক্রমের আকার খুঁজে বের করতে হবে যেখানে ধনাত্মক এবং ঋণাত্মক দুটি পরপর সংখ্যার মধ্যে পার্থক্য। এবং প্রথম পার্থক্যটি ইতিবাচক বা নেতিবাচক হতে পারে।

সুতরাং, যদি ইনপুটটি nums =[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-এর জন্য
  • করুন
    • যদি nums[j]
    • dp[i, 0] =সর্বাধিক dp[i, 0] এবং (dp[j, 1] + 1)
  • অন্যথায় যখন nums[j]> nums[i], তারপর
    • dp[i, 1] =সর্বাধিক dp[i, 1] এবং (dp[j, 0] + 1)
• উত্তর =সর্বাধিক উত্তর, 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