> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/get-the-maximum-score.md).

# Get the Maximum Score

You are given two **sorted** arrays of distinct integers `nums1` and `nums2.`

A **valid** path is defined as follows:

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

*Score* is defined as the sum of uniques values in a valid path.

Return the maximum *score* you can obtain of all possible **valid paths**.

Since the answer may be too large, return it modulo 10^9 + 7.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/07/16/sample_1_1893.png)

```
Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
Output: 30
Explanation: 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 [2,4,6,8,10].
```

**Example 2:**

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

**Example 3:**

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

**Example 4:**

```
Input: nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
Output: 61
```

**Constraints:**

* `1 <= nums1.length <= 10^5`
* `1 <= nums2.length <= 10^5`
* `1 <= nums1[i], nums2[i] <= 10^7`
* `nums1` and `nums2` are strictly increasing.

```java
class Solution {
    long mod = 1_000_000_007;

    public int maxSum(int[] nums1, int[] nums2) {
        // Converting array to sum between 2 similar elements
        List<int[]> arr = new ArrayList<>();
        int p1 = 0, p2 = 0;
        while (p1 < nums1.length && p2 < nums2.length) {
            if (nums1[p1] == nums2[p2]) {
                arr.add(new int[]{p1, p2});
                p1++;
                p2++;
            } else if (nums1[p1] < nums2[p2])
                p1++;
            else
                p2++;
        }
        long[] arr1 = new long[arr.size() + 1];
        long[] arr2 = new long[arr.size() + 1];
        p1 = 0;
        p2 = 0;
        for (int i = 0; i <= arr.size(); i++) {
            long sum1 = 0, sum2 = 0;
            if (i == 0 && i != arr.size()) {
                while (p1 < arr.get(0)[0])
                    sum1 = (sum1 + nums1[p1++]);
                while (p2 < arr.get(0)[1])
                    sum2 = (sum2 + nums2[p2++]);
            } else if (i < arr.size()) {
                while (p1 < arr.get(i)[0])
                    sum1 = (sum1 + nums1[p1++]);
                while (p2 < arr.get(i)[1])
                    sum2 = (sum2 + nums2[p2++]);
            } else {
                while (p1 < nums1.length)
                    sum1 = (sum1 + nums1[p1++]);
                while (p2 < nums2.length)
                    sum2 = (sum2 + nums2[p2++]);
            }
            arr1[i] = sum1;
            arr2[i] = sum2;
        }
        // Now we have to just find the max
        int n = arr1.length;
        long[][] dp = new long[n + 1][2];
        for (int i = 1; i <= n; i++) {
            dp[i][0] = (arr1[i - 1] + Math.max(dp[i - 1][0], dp[i - 1][1]));
            dp[i][1] = (arr2[i - 1] + Math.max(dp[i - 1][0], dp[i - 1][1]));
        }
        return (int) (Math.max(dp[n][0], dp[n][1]) % mod);
    }
}
```