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

मान लीजिए हमारे पास nums नामक संख्याओं की एक लिस्ट है, हमें सबसे लंबे अंकगणितीय सबसीक्वेंस की लंबाई ढूंढनी है। जैसा कि हम जानते हैं, एक अनुक्रम S[i] अंकगणितीय होता है जब S[i+1] - S[i] का मान हर i के लिए समान होता है (0 ≤ i < S का आकार - 1)।

उदाहरण के लिए, यदि इनपुट nums = [1, 4, 7, 10, 13, 20, 16] है, तो आउटपुट 6 होगा, क्योंकि सबसीक्वेंस [1, 4, 7, 10, 13, 16] अंकगणितीय है क्योंकि प्रत्येक लगातार तत्व का अंतर 3 है।

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

इस समस्या को हल करने के लिए हम डायनामिक प्रोग्रामिंग के साथ हैशमैप का उपयोग करेंगे:

• n := arr का आकार
• यदि n <= 1 है, तो n लौटाएं
• res := 0
• dp := एक खाली मैप, डिफ़ॉल्ट मान 1
• i को 1 से n-1 तक लूप चलाएं:
  • j को 0 से i-1 तक लूप चलाएं:
    • diff := arr[i] - arr[j]
    • dp[i, diff] := dp[j, diff] + 1
    • res := max(res, dp[i, diff])
• res लौटाएं

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

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