If you do DFS please just store everything in Long and mod at the end
class Solution {\n    \n    Map a2b = new HashMap<>();\n    Map b2a = new HashMap<>();\n    int MOD = 1000000007;\n    int max = 0;\n    HashMap dp = new HashMa
class Solution {\n    \n    Map<Integer, Integer> a2b = new HashMap<>();\n    Map<Integer, Integer> b2a = new HashMap<>();\n    int MOD = 1000000007;\n    int max = 0;\n    HashMap<Integer, Long> dp = new HashMap<>();\n    \n    public int maxSum(int[] nums1, int[] nums2) {\n        int m = 0;\n        int n = 0;\n        \n        while(m < nums1.length && n < nums2.length){\n            int num1 = nums1[m];\n            int num2 = nums2[n];\n            if(num1 == num2){\n                a2b.put(m,n);\n                b2a.put(n,m);\n                m++;\n                n++;\n            } else if (num1 < num2){\n                m++;\n            } else{\n                n++;\n            }\n        }\n        Long ans = Math.max(dfs(0, nums1, nums2, 1) , \n                            dfs(0, nums1, nums2, 2));\n        ans %= MOD;\n        return ans.intValue();\n    }\n    \n    long dfs (int i, int[] nums1, int[] nums2, int nums){\n        if(nums == 1 && i == nums1.length || nums == 2 && i == nums2.length)\n            return 0;\n        \n        int val = nums == 1 ? nums1[i] : nums2[i];\n        if(dp.get(val) != null){\n            return dp.get(val);\n        }\n        \n        long next = 0;\n        if(nums == 1){\n            next = Math.max(next, dfs(i+1, nums1, nums2, 1));\n            if(a2b.get(i) != null){\n                next = Math.max(next, dfs(a2b.get(i)+1, nums1, nums2, 2));\n            }\n        } else {\n            next = Math.max(next, dfs(i+1, nums1, nums2, 2));\n            if(b2a.get(i) != null){\n                next = Math.max(next, dfs(b2a.get(i)+1, nums1, nums2, 1));\n            }\n        }\n        \n        long ans = next + val;\n        dp.put(val, ans);\n        \n        return dp.get(val);\n    }\n}
['Dynamic Programming', 'Depth-First Search', 'Iterator', 'Java']