Hard

题目描述

给你两个 有序且不相同 的整数数组 nums1 和 nums2。

有效路径 定义如下：

  • 选择数组 nums1 或者 nums2 开始遍历（从下标 0 处开始）。
  • 从左到右遍历当前数组。
  • 如果你遇到了一个在 nums1 和 nums2 中都存在的值，那么你可以切换路径到另一个数组对应数字处，切换行为只能在相同数字处发生（注意在有效路径中重复数字只会被统计一次）。

得分定义为有效路径中不同数字的和。

请你返回所有可能的有效路径中的最大得分。答案很大的话，请你将它对 10^9 + 7 取模后返回。

示例 1：

输入：nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
输出：30
解释：有效路径为：
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10]（从 nums1 开始）
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]（从 nums2 开始）
最大得分为上图中的绿色路径 [2,4,6,8,10]。

示例 2：

输入：nums1 = [1,3,5,7,9], nums2 = [3,5,100]
输出：109
解释：最大得分由路径 [1,3,5,100] 得到。

示例 3：

输入：nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
输出：40
解释：nums1 和 nums2 之间无相同数字。
最大得分由路径 [6,7,8,9,10] 得到。

提示：

  • 1 <= nums1.length, nums2.length <= 10^5
  • 1 <= nums1[i], nums2[i] <= 10^7
  • nums1 和 nums2 都是严格递增的数组。

解题思路

这道题的核心思想是分段贪心。我们需要找到两个数组的公共元素，这些公共元素将路径分割成若干段。在每一段中，我们选择和更大的那条路径，然后在公共元素处进行路径切换。

解题思路：

  1. 双指针遍历：使用两个指针分别遍历两个数组，寻找公共元素。

  2. 分段累积：在遍历过程中，分别累积当前段在两个数组中的元素和。

  3. 贪心选择：当遇到公共元素时，在两段路径中选择和更大的那一段，加入到最终结果中。

  4. 状态转移：每次遇到公共元素，将当前的最大和更新为之前的最大和加上当前段的最大和，然后重置两个段的累积和。

具体算法步骤：

  • 使用双指针 i 和 j 分别指向两个数组的当前位置
  • 维护两个变量 sum1 和 sum2 记录当前段的累积和
  • 当遇到相同元素时，选择 max(sum1, sum2) 加入结果，并重置累积和
  • 最后处理剩余部分，同样选择较大的累积和

时间复杂度： O(m + n)，其中 m 和 n 分别是两个数组的长度 空间复杂度： O(1)，只使用了常数额外空间

代码实现

class Solution {
public:
    int maxSum(vector<int>& nums1, vector<int>& nums2) {
        const int MOD = 1e9 + 7;
        int i = 0, j = 0;
        long long sum1 = 0, sum2 = 0, result = 0;
        
        while (i < nums1.size() && j < nums2.size()) {
            if (nums1[i] < nums2[j]) {
                sum1 += nums1[i++];
            } else if (nums1[i] > nums2[j]) {
                sum2 += nums2[j++];
            } else {
                result += max(sum1, sum2) + nums1[i];
                sum1 = sum2 = 0;
                i++;
                j++;
            }
        }
        
        while (i < nums1.size()) {
            sum1 += nums1[i++];
        }
        
        while (j < nums2.size()) {
            sum2 += nums2[j++];
        }
        
        result += max(sum1, sum2);
        return result % MOD;
    }
};

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        MOD = 10**9 + 7
        i = j = 0
        sum1 = sum2 = result = 0
        
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                sum1 += nums1[i]
                i += 1
            elif nums1[i] > nums2[j]:
                sum2 += nums2[j]
                j += 1
            else:
                result += max(sum1, sum2) + nums1[i]
                sum1 = sum2 = 0
                i += 1
                j += 1
        
        while i < len(nums1):
            sum1 += nums1[i]
            i += 1
        
        while j < len(nums2):
            sum2 += nums2[j]
            j += 1
        
        result += max(sum1, sum2)
        return result % MOD

public class Solution {
    public int MaxSum(int[] nums1, int[] nums2) {
        const int MOD = 1000000007;
        int i = 0, j = 0;
        long sum1 = 0, sum2 = 0, result = 0;
        
        while (i < nums1.Length && j < nums2.Length) {
            if (nums1[i] < nums2[j]) {
                sum1 += nums1[i++];
            } else if (nums1[i] > nums2[j]) {
                sum2 += nums2[j++];
            } else {
                result += Math.Max(sum1, sum2) + nums1[i];
                sum1 = sum2 = 0;
                i++;
                j++;
            }
        }
        
        while (i < nums1.Length) {
            sum1 += nums1[i++];
        }
        
        while (j < nums2.Length) {
            sum2 += nums2[j++];
        }
        
        result += Math.Max(sum1, sum2);
        return (int)(result % MOD);
    }
}

var maxSum = function(nums1, nums2) {
    const MOD = 1e9 + 7;
    let i = 0, j = 0;
    let sum1 = 0, sum2 = 0, result = 0;
    
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            sum1 += nums1[i++];
        } else if (nums1[i] > nums2[j]) {
            sum2 += nums2[j++];
        } else {
            result += Math.max(sum1, sum2) + nums1[i];
            sum1 = sum2 = 0;
            i++;
            j++;
        }
    }
    
    while (i < nums1.length) {
        sum1 += nums1[i++];
    }
    
    while (j < nums2.length) {
        sum2 += nums2[j++];
    }
    
    result += Math.max(sum1, sum2);
    return result % MOD;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(m + n)
空间复杂度O(1)

其中 m 和 n 分别是 nums1 和 nums2 的长度。时间复杂度为线性，因为我们只需要遍历两个数组一次。空间复杂度为常数，因为只使用了固定数量的变量。

相关题目