Package g1501_1600.s1537_get_the_maximum_score

Class Solution

java.lang.Object

g1501_1600.s1537_get_the_maximum_score.Solution

public class Solution
extends Object

1537 - Get the Maximum Score.<p>Hard</p> <p>You are given two <strong>sorted</strong> arrays of distinct integers <code>nums1</code> and <code>nums2.</code></p> <p>A <strong>valid 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 uniques 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⁹ + 7</code>.</p> <p><strong>Example 1:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2020/07/16/sample_1_1893.png" alt="" /></p> <p><strong>Input:</strong> nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]</p> <p><strong>Output:</strong> 30</p> <p><strong>Explanation:</strong> Valid paths:</p> <p>[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10], (starting from nums1)</p> <p>[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10] (starting from nums2)</p> <p>The maximum is obtained with the path in green <strong>[2,4,6,8,10]</strong>.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> nums1 = [1,3,5,7,9], nums2 = [3,5,100]</p> <p><strong>Output:</strong> 109</p> <p><strong>Explanation:</strong> Maximum sum is obtained with the path <strong>[1,3,5,100]</strong>.</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]</p> <p><strong>Output:</strong> 40</p> <p><strong>Explanation:</strong> There are no common elements between nums1 and nums2. Maximum sum is obtained with the path [6,7,8,9,10].</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= nums1.length, nums2.length <= 10⁵</code></li> <li><code>1 <= nums1[i], nums2[i] <= 10⁷</code></li> <li><code>nums1</code> and <code>nums2</code> are strictly increasing.</li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	maxSum(int[] nums1, int[] nums2)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

maxSum

public int maxSum(int[] nums1,
 int[] nums2)