假设我们有两个数组 nums1 和 nums2。有效路径定义如下 -
选择 nums1 或 nums2 进行遍历(从 index-0 开始)。
从左到右遍历数组。
现在,如果我们正在遍历 nums1 和 nums2 中存在的任何值,我们可以将路径更改为另一个数组。这里的分数是有效路径中唯一值的总和。我们必须找到所有可能的有效路径的最高分。如果答案太大,则返回模 10^9+7 的结果。
因此,如果输入类似于 nums1 = [3,5,6,9,11] nums2 = [5,7,9,10],那么输出将为 35,因为 -
从 nums1 开始的有效路径为:[3,5,6,9,11], [3,5,6,9,10], [3,5,7,9,10], [3,5,7, 9,11]
从 nums2 开始的有效路径为:[5,7,9,10], [5,6,9,11], [5,6,9,10], [5,7,9,11]
所以最大值是 [3,5,7,9,11]。
让我们看看以下实现以更好地理解
def solve(nums1, nums2): M, N = len(nums1), len(nums2) sum1, sum2 = 0, 0 i, j = 0, 0 res = 0 while i < M and j < N: if nums1[i] < nums2[j]: sum1 += nums1[i] i += 1 elif nums1[i] > nums2[j]: sum2 += nums2[j] j += 1 else: res += max(sum1, sum2) + nums1[i] i += 1 j += 1 sum1 = 0 sum2 = 0 while i < M: sum1 += nums1[i] i += 1 while j < N: sum2 += nums2[j] j += 1 return (res + max(sum1, sum2)) % 1000000007 nums1 = [3,5,6,9,11] nums2 = [5,7,9,10] print(solve(nums1, nums2))
[3,5,6,9,11], [5,7,9,10]输出结果
35