最大得分

1537. 最大得分

你有两个有序且数组内元素互不相同的数组 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] 得到。

示例 4：

输入：nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
输出：61

提示：

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

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int maxSum(vector<int>& nums1, vector<int>& nums2) { } };

typescript 解法, 执行用时: 176 ms, 内存消耗: 69.2 MB, 提交时间: 2023-09-25 15:37:27

function maxSum(nums1: number[], nums2: number[]): number {
    const sum = (nums: number[], l: number, r: number) => (l < r) && nums.slice(l, r).reduce((s, t) => s + t) || 0;
    const d = new Map(nums1.map((v, k) => [v, k]));
    let ans = 0;
    let [p, q] = [0, 0];
    nums2.forEach((t, j) => {
        if (d.has(t)) {
            const i = <number>d.get(t);
            ans += Math.max(sum(nums1, p, i), sum(nums2, q, j));
            [p, q] = [i, j];
        }
    });
    ans += Math.max(sum(nums1, p, nums1.length), sum(nums2, q, nums2.length));
    return ans % 1000000007
};

rust 解法, 执行用时: 8 ms, 内存消耗: 6 MB, 提交时间: 2023-09-25 15:36:51

use std::collections::{HashMap, HashSet};
impl Solution {
    pub fn max_sum(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let sum = |nums: &Vec<i32>, l, r| nums[l..r].iter().fold(0i64, |s, &t| s + t as i64);
        let d: HashMap<_, _> = nums1.iter().enumerate().map(|(i, &t)| (t, i)).collect();
        let mut ans = 0i64;
        let mut p = 0;
        let mut q = 0;
        let m = 1000000007;
        for j in 0..nums2.len() {
            if let Some(&i) = d.get(&nums2[j]) {
                ans = (ans + sum(&nums1, p, i).max(sum(&nums2, q, j))) % m;
                p = i;
                q = j;
            }
        }
        ((ans + sum(&nums1, p, nums1.len()).max(sum(&nums2, q, nums2.len()))) % m) as i32
    }
}

golang 解法, 执行用时: 100 ms, 内存消耗: 12 MB, 提交时间: 2023-09-25 15:36:25

func maxSum(nums1 []int, nums2 []int) int {
    sum := func(nums []int, l, r int) (s int) {
        for i := l; i < r; i++ {
            s += nums[i]
        }
        return
    }
    max := func(i, j int) int {if i > j {return i}; return j}
    d := map[int]int{}
    for i, t := range nums1 {
        d[t] = i
    }
    ans := 0
    p, q := 0, 0
    m := 1000000007
    for j, t := range nums2 {
        if i, ok := d[t]; ok {
            ans = (ans + max(sum(nums1, p, i), sum(nums2, q, j))) % m
            p, q = i, j
        }
    }
    return (ans + max(sum(nums1, p, len(nums1)), sum(nums2, q, len(nums2)))) % m
}

python3 解法, 执行用时: 92 ms, 内存消耗: 31.6 MB, 提交时间: 2023-09-25 15:35:54

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        d = {t: i for i, t in enumerate(nums1)}
        ans = 0
        p, q = 0, 0
        for j, t in enumerate(nums2):
            if t in d:
                i = d[t]
                ans += max(sum(nums1[p: i]), sum(nums2[q: j]))
                p, q = i, j
        ans += max(sum(nums1[p: ]), sum(nums2[q: ]))
        return ans % 1000000007

    
    def maxSum2(self, nums1: List[int], nums2: List[int]) -> int:
        d1 = {t: i for i, t in enumerate(nums1)}
        d2 = {t: j for j, t in enumerate(nums2)}
        ans = 0
        p, q = 0, 0
        for t in sorted({*nums1} & {*nums2}):
            i, j = d1[t], d2[t]
            ans += max(sum(nums1[p: i]), sum(nums2[q: j]))
            p, q = i, j
        ans += max(sum(nums1[p: ]), sum(nums2[q: ]))
        return ans % 1000000007

python3 解法, 执行用时: 120 ms, 内存消耗: 26.2 MB, 提交时间: 2023-09-25 15:34:33

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

java 解法, 执行用时: 4 ms, 内存消耗: 54.6 MB, 提交时间: 2023-09-25 15:34:01

class Solution {
    public int maxSum(int[] nums1, int[] nums2) {
        final int MOD = 1000000007;
        int m = nums1.length;
        int n = nums2.length;
        long best1 = 0, best2 = 0;
        int i = 0, j = 0;
        while (i < m || j < n) {
            if (i < m && j < n) {
                if (nums1[i] < nums2[j]) {
                    best1 += nums1[i];
                    ++i;
                } else if (nums1[i] > nums2[j]) {
                    best2 += nums2[j];
                    ++j;
                } else {
                    long best = Math.max(best1, best2) + nums1[i];
                    best1 = best2 = best;
                    ++i;
                    ++j;
                }
            } else if (i < m) {
                best1 += nums1[i];
                ++i;
            } else if (j < n) {
                best2 += nums2[j];
                ++j;
            }
        }
        return (int) (Math.max(best1, best2) % MOD);
    }
}

cpp 解法, 执行用时: 92 ms, 内存消耗: 54.7 MB, 提交时间: 2023-09-25 15:33:36

class Solution {
private:
    static constexpr int mod = 1000000007;
    
public:
    int maxSum(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        long long best1 = 0, best2 = 0;
        int i = 0, j = 0;
        while (i < m || j < n) {
            if (i < m && j < n) {
                if (nums1[i] < nums2[j]) {
                    best1 += nums1[i];
                    ++i;
                }
                else if (nums1[i] > nums2[j]) {
                    best2 += nums2[j];
                    ++j;
                }
                else {
                    long long best = max(best1, best2) + nums1[i];
                    best1 = best2 = best;
                    ++i;
                    ++j;
                }
            }
            else if (i < m) {
                best1 += nums1[i];
                ++i;
            }
            else if (j < n) {
                best2 += nums2[j];
                ++j;
            }
        }
        return max(best1, best2) % mod;
    }
};

上一题

下一题

详情