C++ DP solution with detailed explanation
C++ DP solution with detailed explanation\n\nf[i][k] means that we have state index i, visiting k array (k is 0 or 1)\nfor each state, we have two choices\n\n1.
C++ DP solution with detailed explanation\n\n`f[i][k]` means that we have state index `i`, visiting `k` array (k is 0 or 1)\nfor each state, we have two choices\n\n1. we can visit the next item of the `k` array, we get `arr[k][i]` score\n2. If there exist `arr[k ^ 1][x]` so that `arr[k][i] == arr[k ^ 1][x]`, we can also jump to the second array and get `arr[k][i]` score\nWe can use the stategy of binary search and find whether there exists `arr[k ^ 1][x]` and what `x` is, in O(logn) time\n\nWe should maxium the total score.\n\nTime complexity: `O(nlogn)`\nSpace complexity: `O(n)`\n\nThe XOR notation is a trick `0 ^ 1 = 1`, `1 ^ 1 = 0`, because we have two array in total.\n\n```cpp\nclass Solution {\npublic:\n    int maxSum(vector<int>& nums1, vector<int>& nums2) {\n        v[0] = nums1, v[1] = nums2;\n        N = nums1.size(), M = nums2.size();\n        memset(f, 0xff, sizeof f);\n        return max(dfs(0, 0), dfs(0, 1)) % mod;\n    }\nprivate:\n    long long f[100005][2];\n    const int mod = 1e9+7;\n    int N, M;\n    vector<int> v[2];\n    long long dfs(int i, int k) {\n        if (i == v[k].size()) return 0;\n        long long& val = f[i][k];\n        if (val != -1) return val;\n        \n        long long answer = 0;\n        answer = max(answer, v[k][i] + dfs(i + 1, k));\n        auto it = lower_bound(v[k ^ 1].begin(), v[k ^ 1].end(), v[k][i]);\n        if (it != v[k ^ 1].end() && *it == v[k][i]) {\n            answer = max(answer, v[k][i] + dfs(it + 1 - v[k ^ 1].begin(), k ^ 1));\n        }\n        return val = answer;\n    }\n};\n```
[]