[C++] Easy DP Solution
- Pick one path and start traversing, you will either go on path-1 i.e. nums1 or path-2 i.e. nums2.\n- Also store all values and index of both paths in a map, t
**- Pick one path and start traversing, you will either go on path-1 i.e. nums1 or path-2 i.e. nums2.**\n**- Also store all values and index of both paths in a map, to access later**\n**- Each path consist of two options :-**\n\n\t1) pick the current value and keep traversing on same path\n\t2) check if current value exist in alternative, if yes pick current value and switch paths\n\n***Recursive Solution (TLE):***\n```\nclass Solution {\npublic:\n    int help(int index , int path , unordered_map<int,int>&path1 , unordered_map<int,int>&path2 , vector<int>&nums1 , vector<int>&nums2)\n    {\n        if(path == 1)\n        {\n            if(index >= nums1.size() )\n            {\n                return 0;\n            }\n        }\n        else if(path == 2 )\n        {\n            if(index >= nums2.size())\n            {\n                return 0;\n            }\n        }\n        if(path == 1)\n        {\n            int op1 = nums1[index] + help(index+1 , 1 , path1 , path2 , nums1 , nums2 );\n            int op2 = 0;\n            if(path2.find( nums1[index] ) != path2.end())\n            {\n                op2 = nums1[index] + help( path2[nums1[index]]+1 , 2 , path1 , path2 , nums1 , nums2 );\n            }\n            return max(op1,op2);\n        }\n        else\n        {\n            int op1 = nums2[index] + help(index+1 , 2 , path1 , path2 , nums1 , nums2 );\n            int op2 = 0;\n            if(path1.find( nums2[index] ) != path1.end())\n            {\n                op2 = nums2[index] + help( path1[nums2[index]]+1 , 1 , path1 , path2 , nums1 , nums2 );\n            }\n            return max(op1,op2);\n        }\n    }\n    \n    int maxSum(vector<int>& nums1, vector<int>& nums2) {\n        unordered_map<int,int>path1;\n        unordered_map<int,int>path2;\n        \n        for(int i=0;i<nums1.size();i++)\n        {\n            path1[nums1[i]] = i;\n        }\n        \n        for(int i=0;i<nums2.size();i++)\n        {\n            path2[nums2[i]] = i;\n        }\n        \n        int res1 = help(0,1,path1,path2,nums1,nums2);\n        int res2 = help(0,2,path1,path2,nums1,nums2);\n        \n        return max(res1,res2);\n    }\n};\n```\n\n***DP Solution (Accepted) :***\n```\nclass Solution {\npublic:\n    const int mod = 1e9 + 7;\n    long long int help(int index , int path , unordered_map<int,int>&path1 , unordered_map<int,int>&path2 , vector<int>&nums1 , vector<int>&nums2 , vector<vector<long long int>>&dp)\n    {\n        if(path == 1)\n        {\n            if(index >= nums1.size() )\n            {\n                return 0;\n            }\n        }\n        else if(path == 2 )\n        {\n            if(index >= nums2.size())\n            {\n                return 0;\n            }\n        }\n        \n        if(dp[index][path]!=-1)\n        {\n            return dp[index][path];\n        }\n        \n        if(path == 1)\n        {\n            long long int op1 = nums1[index] + help(index+1 , 1 , path1 , path2 , nums1 , nums2 , dp);\n            long long int op2 = 0;\n            if(path2.find( nums1[index] ) != path2.end())\n            {\n                op2 = nums1[index] + help( path2[nums1[index]]+1 , 2 , path1 , path2 , nums1 , nums2 , dp);\n            }\n            return dp[index][path] = max(op1,op2);\n        }\n        else\n        {\n            long long int op1 = nums2[index] + help(index+1 , 2 , path1 , path2 , nums1 , nums2 , dp);\n            long long int op2 = 0;\n            if(path1.find( nums2[index] ) != path1.end())\n            {\n                op2 = nums2[index] + help( path1[nums2[index]]+1 , 1 , path1 , path2 , nums1 , nums2 , dp);\n            }\n            return dp[index][path] = max(op1,op2);\n        }\n    }\n    \n    int maxSum(vector<int>& nums1, vector<int>& nums2) {\n        unordered_map<int,int>path1;\n        unordered_map<int,int>path2;\n        \n        for(int i=0;i<nums1.size();i++)\n        {\n            path1[nums1[i]] = i;\n        }\n        \n        for(int i=0;i<nums2.size();i++)\n        {\n            path2[nums2[i]] = i;\n        }\n         \n        int maxLen = max(nums1.size(),nums2.size());\n        vector<vector<long long int>>dp(maxLen+1,vector<long long int>(2+1,-1));\n        \n        long long int res1 = (help(0,1,path1,path2,nums1,nums2,dp))%mod;\n        long long int res2 = (help(0,2,path1,path2,nums1,nums2,dp))%mod;\n        \n        return max(res1,res2)%mod;\n    }\n};\n```\n
['Dynamic Programming', 'Recursion', 'Memoization', 'C']