<p>You are given two <strong>sorted</strong> arrays of distinct integers <code>nums1</code> and <code>nums2</code>.</p>

<p>A <strong>valid<strong><em> </em></strong>path</strong> is defined as follows:</p>

<ul>
	<li>Choose array <code>nums1</code> or <code>nums2</code> to traverse (from index-0).</li>
	<li>Traverse the current array from left to right.</li>
	<li>If you are reading any value that is present in <code>nums1</code> and <code>nums2</code> you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).</li>
</ul>

<p>The <strong>score</strong> is defined as the sum of unique values in a valid path.</p>

<p>Return <em>the maximum score you can obtain of all possible <strong>valid paths</strong></em>. Since the answer may be too large, return it modulo <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/07/16/sample_1_1893.png" style="width: 500px; height: 151px;" />
<pre>
<strong>Input:</strong> nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
<strong>Output:</strong> 30
<strong>Explanation:</strong> Valid paths:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],  (starting from nums1)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]    (starting from nums2)
The maximum is obtained with the path in green <strong>[2,4,6,8,10]</strong>.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1,3,5,7,9], nums2 = [3,5,100]
<strong>Output:</strong> 109
<strong>Explanation:</strong> Maximum sum is obtained with the path <strong>[1,3,5,100]</strong>.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
<strong>Output:</strong> 40
<strong>Explanation:</strong> There are no common elements between nums1 and nums2.
Maximum sum is obtained with the path [6,7,8,9,10].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums1.length, nums2.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums1[i], nums2[i] &lt;= 10<sup>7</sup></code></li>
	<li><code>nums1</code> and <code>nums2</code> are strictly increasing.</li>
</ul>

#define MOD (7 + 1000000000)
class Solution {
    vector<long long> dp1;
    vector<long long> dp2;
    int find(vector<int> &arr,int i,int j,int value){
        while(i<=j){
            int mid=(i+j)/2;
            if(value==arr[mid]){
                return mid;
            }
            else if(value<arr[mid]){
                j=mid-1;
            }
            else if(value>arr[mid]){
                i=mid+1;
            }
        }
        return -1;
    }
public:
    long long count(int idx1, int idx2, bool on1, vector<int>& nums1,
                    vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        long long ans = 0;
        if (idx1 >= n1 and idx2 >= n2)
            return 0;
        if (idx1 >= n1 or idx2 >= n2) {
            if (idx1 >= n1 and !on1) {
                dp2[idx2]=
                ans = accumulate(nums2.begin() + idx2, nums2.end(), 0);
                return ans;
            } else if (idx2 >= n2 and on1) {
                dp1[idx1]=
                ans = accumulate(nums1.begin() + idx1, nums1.end(), 0);
                return ans;
            }
            return 0;
        }
        if (on1 and dp1[idx1] != -1)
            return dp1[idx1];
        if (!on1 and dp2[idx2] != -1)
            return dp2[idx2];
        if (on1) {
            auto it = find(nums2, idx2, n2-1, nums1[idx1]);
            if (it != -1) {
                ans = nums1[idx1]+count(idx1 + 1, it+1, false, nums1, nums2);
            }
            dp1[idx1] =
            ans = max(ans,
                      nums1[idx1] + count(idx1 + 1, idx2, true, nums1, nums2));
        } else {
            auto it = find(nums1 , idx1, n1-1, nums2[idx2]);
            if (it != -1) {
                ans = nums2[idx2]+count(it +1, idx2 + 1, true, nums1, nums2);
            }
            dp2[idx2] =
            ans = max(ans,
                      nums2[idx2] + count(idx1, idx2 + 1, false, nums1, nums2));
        }
        return ans;
    }
    int maxSum(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        dp1.clear();
        dp1.resize(n1, -1);
        dp2.clear();
        dp2.resize(n2, -1);
        long long ans1 = count(0, 0, true, nums1, nums2);
        dp1.clear();
        dp1.resize(n1, -1);
        dp2.clear();
        dp2.resize(n2, -1);
        long long ans2 = count(0, 0, false, nums1, nums2);
        return max(ans1, ans2) % MOD;
    }
};
67885