Formatted question description: https://leetcode.ca/all/1537.html

1537. Get the Maximum Score (Hard)

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:

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.

Related Topics:
Dynamic Programming

Solution 1. DP

Intuition:

If the two arrays doens’t have any number in common, the result is simply max(sum(A), sum(B)).

So only the common numbers shared between these two arrays changes the algorithm a bit.

Algorithm:

Considering the subproblem with A[0..i)] and B[0..j)]:

Let sa be the best score we can get if we pick A[i] as the last element.

Let sb be the best score we can get if we pick B[j] as the last element.

If A[i] < B[j], we can only extend the sa by adding A[i] to it.

If A[i] > B[j], we can only extend the sb by adding B[j] to it.

If A[i] == B[j], we pick the greatest out of the following two options and set it back to sa and sb.

  • extend sa by adding A[i]
  • extend sb by adding B[j]

In the end, max(sa, sb) is the answer

// OJ: https://leetcode.com/problems/get-the-maximum-score/

// Time: O(M + N)
// Space: O(1)
class Solution {
public:
    int maxSum(vector<int>& A, vector<int>& B) {
        long M = A.size(), N = B.size(), sa = 0, sb = 0, mod = 1e9+7, i = 0, j = 0;
        while (i < M && j < N) {
            if (A[i] < B[j]) sa += A[i++];
            else if (A[i] > B[j]) sb += B[j++];
            else sa = sb = max(sa + A[i++], sb + B[j++]);
        }
        while (i < M) sa += A[i++];
        while (j < N) sb += B[j++];
        return max(sa, sb) % mod;
    }
};

Java

class Solution {
    public int maxSum(int[] nums1, int[] nums2) {
        final int MODULO = 1000000007;
        int length1 = nums1.length, length2 = nums2.length;
        long[] dp1 = new long[length1];
        long[] dp2 = new long[length2];
        dp1[0] = nums1[0];
        dp2[0] = nums2[0];
        int index1 = 0, index2 = 0;
        while (index1 < length1 && index2 < length2) {
            int num1 = nums1[index1], num2 = nums2[index2];
            if (index1 > 0)
                dp1[index1] = Math.max(dp1[index1], dp1[index1 - 1] + num1);
            if (index2 > 0)
                dp2[index2] = Math.max(dp2[index2], dp2[index2 - 1] + num2);
            if (num1 == num2) {
                long curMax = Math.max(dp1[index1], dp2[index2]);
                dp1[index1] = curMax;
                dp2[index2] = curMax;
                index1++;
                index2++;
            } else if (num1 < num2)
                index1++;
            else
                index2++;
        }
        while (index1 < length1) {
            if (index1 > 0)
                dp1[index1] = Math.max(dp1[index1], dp1[index1 - 1] + nums1[index1]);
            index1++;
        }
        while (index2 < length2) {
            if (index2 > 0)
                dp2[index2] = Math.max(dp2[index2], dp2[index2 - 1] + nums2[index2]);
            index2++;
        }
        long maxSum = Math.max(dp1[length1 - 1], dp2[length2 - 1]);
        return (int) (maxSum % MODULO);
    }
}

All Problems

All Solutions