C++ में लॉन्गेस्ट अंकगणितीय अनुक्रम (Longest Arithmetic Sequence)

मान लीजिए हमारे पास पूर्णांकों का एक ऐरे A है, हमें A में सबसे लंबे अंकगणितीय उपअनुक्रम (arithmetic subsequence) की लंबाई लौटानी है। जैसा कि आप जानते हैं, A का एक उपअनुक्रम A[i_1], A[i_2], ..., A[i_k] की सूची है जहां 0 ≤ i_1 < i_2 < ... < i_k ≤ A.length - 1, और एक अनुक्रम B अंकगणितीय होता है जब B[i+1] - B[i] सभी समान मान होते हैं (0 ≤ i < B.length - 1 के लिए)।

उदाहरण के लिए, यदि इनपुट [9,4,7,2,10] है, तो आउटपुट 3 होगा। क्योंकि सबसे लंबा उपअनुक्रम [4,7,10] है।

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

1. एक मैप dp बनाएं, n := A का आकार, ret := 2 सेट करें

2. i को 0 से n-1 तक लूप चलाएं

3. j को 0 से i-1 तक लूप चलाएं

4. diff := A[j] - A[i] की गणना करें

5. dp[i][diff] := 1 + dp[j][diff] सेट करें

6. ret := max(1 + dp[i][diff], ret) अपडेट करें

7. अंत में ret लौटाएं

C++ कार्यान्वयन

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    int longestArithSeqLength(vector<int>& A) { 
        unordered_map<int, unordered_map<int, int>> dp; 
        int n = A.size(); 
        int ret = 2; 
        for(int i = 0; i < n; i++){ 
            for(int j = 0; j < i; j++){ 
                int diff = A[j] - A[i]; 
                dp[i][diff] = 1 + dp[j][diff]; 
                ret = max(1 + dp[i][diff], ret); 
            } 
        } 
        return ret; 
    } 
}; 

int main(){ 
    vector<int> v1 = {9,4,7,2,10}; 
    Solution ob; 
    cout << (ob.longestArithSeqLength(v1)); 
    return 0; 
}

इनपुट

[9,4,7,2,10]

आउटपुट

3