Get the Maximum Score

Problem#

Two strictly-increasing arrays nums1, nums2. A valid path starts at index 0 of either array, may jump to the other array at any shared value, and must end at the last index of either array. Return the maximum path sum mod 10⁹ + 7.

Examples#

nums1 = [2,4,5,8,10], nums2 = [4,6,8,9] → 30 (path: 2 → 4 → 6 → 8 → 10)

Constraints#

1 <= n, m <= 10^5, values up to 10⁷.

Hints#

Hint 1

At every shared value, you can freely choose the larger of the two side sums accumulated since the last shared value.

Approach#

Two pointers merge through the arrays. Maintain running sums s1, s2 since the last shared value. When nums1[i] == nums2[j], both pointers advance; commit max(s1, s2) + nums1[i] to the answer and reset both running sums to zero.

Solution#

class Solution {
public:
    int maxSum(vector<int>& nums1, vector<int>& nums2) {
        const int MOD = 1'000'000'007;
        long long s1 = 0, s2 = 0, ans = 0;
        int i = 0, j = 0;
        const int n = nums1.size(), m = nums2.size();
        while (i < n && j < m) {
            if (nums1[i] < nums2[j]) s1 += nums1[i++];
            else if (nums1[i] > nums2[j]) s2 += nums2[j++];
            else {
                ans += max(s1, s2) + nums1[i];
                s1 = s2 = 0;
                ++i; ++j;
            }
        }
        while (i < n) s1 += nums1[i++];
        while (j < m) s2 += nums2[j++];
        ans += max(s1, s2);
        return ans % MOD;
    }
};

func maxSum(nums1 []int, nums2 []int) int {
    const MOD = 1_000_000_007
    var s1, s2, ans int64
    i, j := 0, 0
    n, m := len(nums1), len(nums2)
    maxI64 := func(a, b int64) int64 {
        if a > b {
            return a
        }
        return b
    }
    for i < n && j < m {
        if nums1[i] < nums2[j] {
            s1 += int64(nums1[i])
            i++
        } else if nums1[i] > nums2[j] {
            s2 += int64(nums2[j])
            j++
        } else {
            ans += maxI64(s1, s2) + int64(nums1[i])
            s1, s2 = 0, 0
            i++
            j++
        }
    }
    for i < n {
        s1 += int64(nums1[i])
        i++
    }
    for j < m {
        s2 += int64(nums2[j])
        j++
    }
    ans += maxI64(s1, s2)
    return int(ans % MOD)
}

from typing import List

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

function maxSum(nums1, nums2) {
    const MOD = 1_000_000_007n;
    let s1 = 0n, s2 = 0n, ans = 0n;
    let i = 0, j = 0;
    const n = nums1.length, m = nums2.length;
    while (i < n && j < m) {
        if (nums1[i] < nums2[j]) {
            s1 += BigInt(nums1[i++]);
        } else if (nums1[i] > nums2[j]) {
            s2 += BigInt(nums2[j++]);
        } else {
            ans += (s1 > s2 ? s1 : s2) + BigInt(nums1[i]);
            s1 = 0n;
            s2 = 0n;
            i++;
            j++;
        }
    }
    while (i < n) s1 += BigInt(nums1[i++]);
    while (j < m) s2 += BigInt(nums2[j++]);
    ans += (s1 > s2 ? s1 : s2);
    return Number(ans % MOD);
}

class Solution {
    public int maxSum(int[] nums1, int[] nums2) {
        final int MOD = 1_000_000_007;
        long s1 = 0, s2 = 0, ans = 0;
        int i = 0, j = 0;
        int n = nums1.length, m = nums2.length;
        while (i < n && j < m) {
            if (nums1[i] < nums2[j]) {
                s1 += nums1[i++];
            } else if (nums1[i] > nums2[j]) {
                s2 += nums2[j++];
            } else {
                ans += Math.max(s1, s2) + nums1[i];
                s1 = 0;
                s2 = 0;
                i++;
                j++;
            }
        }
        while (i < n) s1 += nums1[i++];
        while (j < m) s2 += nums2[j++];
        ans += Math.max(s1, s2);
        return (int) (ans % MOD);
    }
}

function maxSum(nums1: number[], nums2: number[]): number {
    const MOD = 1_000_000_007n;
    let s1 = 0n, s2 = 0n, ans = 0n;
    let i = 0, j = 0;
    const n = nums1.length, m = nums2.length;
    while (i < n && j < m) {
        if (nums1[i] < nums2[j]) {
            s1 += BigInt(nums1[i++]);
        } else if (nums1[i] > nums2[j]) {
            s2 += BigInt(nums2[j++]);
        } else {
            ans += (s1 > s2 ? s1 : s2) + BigInt(nums1[i]);
            s1 = 0n;
            s2 = 0n;
            i++;
            j++;
        }
    }
    while (i < n) s1 += BigInt(nums1[i++]);
    while (j < m) s2 += BigInt(nums2[j++]);
    ans += (s1 > s2 ? s1 : s2);
    return Number(ans % MOD);
}

Editorial#

The arrays are strictly increasing, so a merge-style walk classifies each element as exclusive to its side until a shared value is found. Between consecutive shared values the optimal path picks the heavier side — switching mid-segment is impossible since there’s no shared element to jump from. The modulo is taken at the end (using long long keeps intermediate sums exact, since values ≤ 10⁷ × length 10⁵ = 10¹², well within signed 64-bit).

Complexity#

Time: O(n + m) — merge walk.
Space: O(1).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#