Get the maximum score

Array Two Pointers Dynamic Programming Greedy

40.8% acceptance

Feb 25, 2026

1068

You are given two sorted arrays of distinct integers nums1 and nums2. A valid path is defined as follows: Choose array nums1 or nums2 to traverse (from index-0). Traverse the current array from left to right. If you are reading any value that is present in nums1 and nums2 you are allowed to change your path to the other array. The score is defined as the sum of unique values in a valid path. Return the maximum score you can obtain of all possible valid paths. Since the answer may be too large, return it modulo 109 + 7.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_sum(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let (m, n) = (nums1.len(), nums2.len());
    let mut i = 0; let mut j = 0;
    let mut acc1: i64 = 0; let mut acc2: i64 = 0;
    while i < m || j < n {
      if i == m {
        acc2 += nums2[j] as i64; j += 1;
      } else if j == n {
        acc1 += nums1[i] as i64; i += 1;
      } else if nums1[i] < nums2[j] {
        acc1 += nums1[i] as i64; i += 1;
      } else if nums1[i] > nums2[j] {
        acc2 += nums2[j] as i64; j += 1;
      } else {
        // Common element: take the best path + this element
        let mx = acc1.max(acc2) + nums1[i] as i64;
        acc1 = mx; acc2 = mx;
        i += 1; j += 1;
      }
    }
    (acc1.max(acc2) % MOD) as i32
  }
}