मान लीजिए हमने A और B के पूर्णांकों को (दिए गए क्रम में) दो अलग-अलग क्षैतिज रेखाओं पर लिखा है। अब, हम कनेक्टिंग लाइनें खींच सकते हैं: A[i] और B[j] को जोड़ने वाली एक सीधी रेखा जैसे कि:
A[i] == B[j];
खींची गई रेखा किसी अन्य कनेक्टिंग (गैर-क्षैतिज) रेखा को प्रतिच्छेद नहीं करती।
ध्यान रखें कि कनेक्टिंग लाइनें एंडपॉइंट्स पर भी प्रतिच्छेद नहीं कर सकतीं - प्रत्येक संख्या केवल एक कनेक्टिंग लाइन से संबंधित हो सकती है। अधिकतम कनेक्टिंग लाइनों की संख्या खोजें।
उदाहरण के लिए, यदि इनपुट [1,4,2] और [1,2,4] है, तो आउटपुट 2 होगा।
समाधान दृष्टिकोण
एक solve() विधि परिभाषित करें जो i, j, ऐरे A, B और मैट्रिक्स dp लेती है
यदि i या j सीमा से बाहर है तो 0 लौटाएं
nj := j से शुरू करके B में A[i] खोजें
पाए जाने पर temp := 1, अन्यथा 0
ret := max(solve(i+1, j), temp + solve(i+1, nj+1)) की गणना करें
dp[i][j] := ret स्टोर करें और लौटाएं
मुख्य विधि से dp मैट्रिक्स बनाकर solve(0, 0) कॉल करें
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(int i, int j, vector<int>& A, vector<int>& B, vector<vector<int>>& dp){
if(i >= A.size()) return 0;
if(j >= B.size()) return 0;
if(dp[i][j] != -1) return dp[i][j];
int nj = j;
while(nj < B.size() && B[nj] != A[i]) nj++;
int ret = max(solve(i + 1, j, A, B, dp), (nj < B.size() ? 1 : 0) + solve(i + 1, nj + 1, A, B, dp));
return dp[i][j] = ret;
}
int maxUncrossedLines(vector<int>& A, vector<int>& B) {
int n = A.size();
int m = B.size();
vector<vector<int>> dp(n, vector<int>(m, -1));
return solve(0, 0, A, B, dp);
}
};
int main(){
vector<int> v1 = {1,4,2};
vector<int> v2 = {1,2,4};
Solution ob;
cout << (ob.maxUncrossedLines(v1, v2));
return 0;
}
इनपुट
[1,4,2] [1,2,4]
आउटपुट
2
