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

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

• n :=गिरफ्तारी का आकार
• यदि n <=1, तो
  • वापसी n
• res :=0
• dp :=एक खाली नक्शा, कुंजी न मिलने पर डिफ़ॉल्ट रूप से यह 1 स्टोर करेगा
• 1 से n-1 की श्रेणी में i के लिए
  • जे के लिए 0 से i-1 की श्रेणी में, करें
    • diff :=arr[i] - arr[j]
    • dp[i, diff] :=dp[j, diff] + 1
    • res :=अधिकतम res और dp[i, diff
• रिटर्न रेस

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

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

from collections import defaultdict
class Solution:
   def solve(self, arr):
      n = len(arr)
      if n <= 1:
         return n
      res = 0
      dp = defaultdict(lambda: 1)
      for i in range(1, n):
         for j in range(i):
            diff = arr[i] - arr[j]
            dp[i, diff] = dp[j, diff] + 1
            res = max(res, dp[i, diff])
      return res
ob = Solution()
nums = [1, 4, 7, 10, 13, 20, 16]
print(ob.solve(nums))

इनपुट

[1, 4, 7, 10, 13, 20, 16]

आउटपुट

6