Skip to main content
Back to problems
#2321
Hard Algorithms

Maximum score of spliced array

Array Dynamic Programming
58.3% acceptance
Feb 25, 2026
837
16
You are given two 0-indexed integer arrays nums1 and nums2, both of length n. You can choose left and right and swap subarray nums1[left..=right] with nums2[left..=right]. The score of the arrays is the maximum of sum(nums1) and sum(nums2). Return the maximum possible score.

Solution

Rust
Time O(n)
Space O(1)
LeetCode
solution.rs 
impl Solution {
  pub fn maximums_spliced_array(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
    let sum1: i32 = nums1.iter().sum();
    let sum2: i32 = nums2.iter().sum();
    let n = nums1.len();

    // Kadane's algorithm to find max subarray gain when swapping from b into a
    let max_gain = |a: &[i32], b: &[i32]| -> i32 {
      let mut best = 0i32;
      let mut cur = 0i32;
      for i in 0..n {
        cur = (cur + b[i] - a[i]).max(0);
        best = best.max(cur);
      }
      best
    };

    (sum1 + max_gain(&nums1, &nums2)).max(sum2 + max_gain(&nums2, &nums1))
  }
}