# Get the Maximum Score
**Difficulty:** HARD
[External](https://leetcode.com/problems/get-the-maximum-score)
Canonical: https://scaleengineer.com/dsa/problems/get-the-maximum-score
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Intuit](https://scaleengineer.com/companies/intuit), [Mindtickle](https://scaleengineer.com/companies/mindtickle)
---
## Problem
You are given two **sorted** arrays of distinct integers `nums1` and `nums2`.

A **validpath** 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).

The **score** is defined as the sum of unique 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 `109 + 7`.

**Example 1:**

![](https://assets.glich.co/dsa/get-the-maximum-score/image0.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].

**Constraints:**

* `1 <= nums1.length, nums2.length <= 105`
* `1 <= nums1[i], nums2[i] <= 107`
* `nums1` and `nums2` are strictly increasing.

# Approaches
## Dynamic Programming with Memoization
This approach models the problem as finding the longest path from the start of either array. We can define a recursive function that calculates the maximum score from a given position in a given array. Since this recursive structure involves many overlapping subproblems (calculating the score from the same point multiple times), we can use memoization (a form of dynamic programming) to store the results of these subproblems and avoid redundant computations.
**Time:** O(N * log(M) + M * log(N)). For each of the N states in `nums1`, we may perform a binary search on `nums2` (O(log M)). Similarly, for each of the M states in `nums2`, we may perform a binary search on `nums1` (O(log N)). Since each state is computed only once due to memoization, this is the total time complexity. · **Space:** O(N + M), where N and M are the lengths of `nums1` and `nums2`. This space is used for the memoization arrays `memo1` and `memo2`, and for the recursion stack.
**Pros:** Conceptually straightforward as it directly translates the problem's recursive definition.; Guaranteed to find the correct optimal solution.
**Cons:** Significantly less efficient in terms of time complexity compared to the two-pointer approach.; The recursive implementation can lead to a `StackOverflowError` for very large inputs due to deep recursion. An iterative DP version would be safer but more complex to implement.; Requires extra space for the memoization tables and the recursion stack.
### Explanation
We can frame this problem recursively. The maximum score from any point `i` in an array is the value `array[i]` plus the maximum score achievable from the next steps. The next step can either be `array[i+1]` or, if `array[i]` is a common element, we can switch to the other array from the corresponding position.

This leads to overlapping subproblems. For instance, we might need to calculate the maximum score from `nums1[k]` multiple times through different paths. Dynamic programming with memoization is a perfect fit here.

We'll use two arrays, `memo1` and `memo2`, to store the calculated maximum scores starting from each index of `nums1` and `nums2`, respectively. The recursive function will first check the memoization table before performing any computation. To find if an element is common and get its index in the other array, we can use binary search, which is efficient because the arrays are sorted.

```java
class Solution {
    long[] memo1;
    long[] memo2;
    int MOD = 1_000_000_007;
    int[] n1, n2;

    public int maxSum(int[] nums1, int[] nums2) {
        this.n1 = nums1;
        this.n2 = nums2;
        memo1 = new long[nums1.length];
        memo2 = new long[nums2.length];
        java.util.Arrays.fill(memo1, -1);
        java.util.Arrays.fill(memo2, -1);

        // We need to find the max score starting from index 0 of either array
        long maxScore = Math.max(solve(0, true), solve(0, false));

        return (int) (maxScore % MOD);
    }

    private long solve(int index, boolean isNums1) {
        if (isNums1) {
            if (index >= n1.length) return 0;
            if (memo1[index] != -1) return memo1[index];

            long currentVal = n1[index];
            // Option 1: Continue in nums1
            long res = currentVal + solve(index + 1, true);

            // Check for Option 2: Switch to nums2 if possible
            int otherIndex = java.util.Arrays.binarySearch(n2, (int)currentVal);
            if (otherIndex >= 0) {
                res = Math.max(res, currentVal + solve(otherIndex + 1, false));
            }
            return memo1[index] = res;
        } else {
            if (index >= n2.length) return 0;
            if (memo2[index] != -1) return memo2[index];

            long currentVal = n2[index];
            // Option 1: Continue in nums2
            long res = currentVal + solve(index + 1, false);

            // Check for Option 2: Switch to nums1 if possible
            int otherIndex = java.util.Arrays.binarySearch(n1, (int)currentVal);
            if (otherIndex >= 0) {
                res = Math.max(res, currentVal + solve(otherIndex + 1, true));
            }
            return memo2[index] = res;
        }
    }
}
```
### Algorithm
- We define a recursive function, let's call it `solve(index, isNums1)`, which calculates the maximum score starting from `index` in either `nums1` (if `isNums1` is true) or `nums2`.
- To avoid recomputing results for the same state (e.g., `solve(5, true)`), we use two memoization arrays, `memo1` for `nums1` and `memo2` for `nums2`.
- **Base Case:** If the `index` goes out of bounds for the respective array, the path ends, so we return 0.
- **Memoization Check:** Before computing, we check if the result for the current state is already stored in our memoization table. If so, we return the stored value.
- **Recursive Step for `solve(i, true)` (i.e., for `nums1[i]`):**
  1. The score from this point will include `nums1[i]`. The default next step is to continue in `nums1`, so we recursively call `solve(i + 1, true)`.
  2. We then check if `nums1[i]` is a common element by searching for it in `nums2`. A binary search is efficient for this since `nums2` is sorted.
  3. If `nums1[i]` is found in `nums2` at index `j`, we have a choice: either continue in `nums1` or switch to `nums2`. We calculate the score for switching, which would be `nums1[i] + solve(j + 1, false)`.
  4. We take the maximum of the two options (staying vs. switching).
  5. Store the computed maximum score in `memo1[i]` and return it.
- The logic for `solve(j, false)` (for `nums2`) is symmetrical.
- The final answer is the maximum of starting from the beginning of `nums1` or `nums2`, i.e., `max(solve(0, true), solve(0, false))`. All additions should be done using `long` to prevent overflow, and the final result is taken modulo `10^9 + 7`.

## Two Pointers (Greedy Approach)
This is a highly efficient greedy approach that leverages the fact that both input arrays are sorted. We can think of the paths as being composed of segments that lie between common elements (or from the start/to the end of the arrays). At each common element, we have a choice point. To maximize the total score, it's always optimal to choose the path segment that has a larger sum leading up to that common point. We can traverse both arrays simultaneously using two pointers to identify these segments and common points, making the greedy choice at each step.
**Time:** O(N + M), where N and M are the lengths of `nums1` and `nums2`. This is because each pointer, `i` and `j`, traverses its respective array at most once in a single pass. · **Space:** O(1). We only use a constant number of extra variables to store pointers and sums, regardless of the input size.
**Pros:** Extremely efficient, providing an optimal linear time solution.; Constant space complexity, making it very memory-efficient.; The logic is clean and avoids the complexities of recursion and potential stack overflow issues.
**Cons:** The greedy logic might be slightly less intuitive to derive initially compared to a direct recursive approach.
### Explanation
The core idea is to break down the problem into segments. A segment is a sequence of numbers in one array between two consecutive common elements. At every common element, we have the choice to switch from one array to the other. The greedy strategy is that to maximize the total sum, at each such junction, we should always come from the path that has accumulated a larger sum so far.

We can implement this efficiently using two pointers, one for each array. We advance the pointers, summing up elements for each array's current segment. When the pointers meet at a common value, we compare the segment sums, add the larger one to our total score, add the common value itself, and then reset the segment sums to start fresh for the next part of the journey.

```java
class Solution {
    public int maxSum(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        long sum1 = 0;
        long sum2 = 0;
        long ans = 0;
        int i = 0;
        int j = 0;
        int MOD = 1_000_000_007;

        while (i < n && j < m) {
            if (nums1[i] < nums2[j]) {
                sum1 += nums1[i];
                i++;
            } else if (nums2[j] < nums1[i]) {
                sum2 += nums2[j];
                j++;
            } else { // Common element found
                // Choose the path with the maximum sum so far
                ans += Math.max(sum1, sum2) + nums1[i];
                // Reset sums for the next segment
                sum1 = 0;
                sum2 = 0;
                i++;
                j++;
            }
        }

        // Add remaining elements from nums1, if any
        while (i < n) {
            sum1 += nums1[i];
            i++;
        }

        // Add remaining elements from nums2, if any
        while (j < m) {
            sum2 += nums2[j];
            j++;
        }

        // Add the maximum of the last segment sums
        ans += Math.max(sum1, sum2);

        return (int) (ans % MOD);
    }
}
```
### Algorithm
- Initialize two pointers, `i` for `nums1` and `j` for `nums2`, both at 0.
- Initialize two `long` variables, `sum1` and `sum2`, to 0. These will store the sums of the current path segments in each array.
- Initialize a `long` variable `ans` to 0, which will accumulate the final maximum score.
- Iterate with a `while` loop as long as both pointers `i` and `j` are within their respective array bounds.
  - **Case 1: `nums1[i] < nums2[j]`**: The element `nums1[i]` is not a common point. Add it to the current segment sum for `nums1` (`sum1 += nums1[i]`) and advance the `i` pointer (`i++`).
  - **Case 2: `nums2[j] < nums1[i]`**: Similarly, add `nums2[j]` to `sum2` and advance the `j` pointer.
  - **Case 3: `nums1[i] == nums2[j]`**: A common element is found. This is a point where we can switch paths. To maximize the score, we choose the segment with the larger sum (`Math.max(sum1, sum2)`), add it to our total answer `ans`, and also add the value of the common element itself. After this, we reset `sum1` and `sum2` to 0 for the next segments and advance both pointers `i` and `j`.
- After the loop, one of the arrays might still have unvisited elements. These form the final segment of a possible path. We iterate through the remainder of `nums1` (if any) adding to `sum1`, and the remainder of `nums2` (if any) adding to `sum2`.
- Finally, we add the larger of these two final segment sums (`Math.max(sum1, sum2)`) to our total answer `ans`.
- Return `ans` modulo `10^9 + 7`.

# Solutions
### Java

```java
class Solution { public int maxSum ( int [] nums1 , int [] nums2 ) { final int mod = ( int ) 1 e9 + 7 ; int m = nums1 . length , n = nums2 . length ; int i = 0 , j = 0 ; long f = 0 , g = 0 ; while ( i < m || j < n ) { if ( i == m ) { g += nums2 [ j ++]; } else if ( j == n ) { f += nums1 [ i ++]; } else if ( nums1 [ i ] < nums2 [ j ]) { f += nums1 [ i ++]; } else if ( nums1 [ i ] > nums2 [ j ]) { g += nums2 [ j ++]; } else { f = g = Math . max ( f , g ) + nums1 [ i ]; i ++; j ++; } } return ( int ) ( Math . max ( f , g ) % mod ); } }
```

### CPP

```cpp
class Solution { public: int maxSum ( vector < int >& nums1 , vector < int >& nums2 ) { const int mod = 1e9 + 7 ; int m = nums1 . size (), n = nums2 . size (); int i = 0 , j = 0 ; long long f = 0 , g = 0 ; while ( i < m || j < n ) { if ( i == m ) { g += nums2 [ j ++ ]; } else if ( j == n ) { f += nums1 [ i ++ ]; } else if ( nums1 [ i ] < nums2 [ j ]) { f += nums1 [ i ++ ]; } else if ( nums1 [ i ] > nums2 [ j ]) { g += nums2 [ j ++ ]; } else { f = g = max ( f , g ) + nums1 [ i ]; i ++ ; j ++ ; } } return max ( f , g ) % mod ; } };
```

### Python

```python
class Solution : def maxSum ( self , nums1 : List [ int ], nums2 : List [ int ]) -> int : mod = 10 ** 9 + 7 m , n = len ( nums1 ), len ( nums2 ) i = j = 0 f = g = 0 while i < m or j < n : if i == m : g += nums2 [ j ] j += 1 elif j == n : f += nums1 [ i ] i += 1 elif nums1 [ i ] < nums2 [ j ]: f += nums1 [ i ] i += 1 elif nums1 [ i ] > nums2 [ j ]: g += nums2 [ j ] j += 1 else : f = g = max ( f , g ) + nums1 [ i ] i += 1 j += 1 return max ( f , g ) % mod
```