Skip to main content
Back to problems
#1031
Medium Algorithms

Maximum sum of two non overlapping subarrays

Array Dynamic Programming Sliding Window
60.8% acceptance
Feb 25, 2026
2661
88
Given an integer array nums and two integers firstLen and secondLen, return the maximum sum of elements in two non-overlapping subarrays with lengths firstLen and secondLen. The array with length firstLen could occur before or after the array with length secondLen, but they have to be non-overlapping. A subarray is a contiguous part of an array.

Solution

Rust
Time O(n)
Space O(n)
LeetCode
solution.rs 
impl Solution {
  pub fn max_sum_two_no_overlap(nums: Vec<i32>, first_len: i32, second_len: i32) -> i32 {
    let n = nums.len();
    let fl = first_len as usize;
    let sl = second_len as usize;
    let mut prefix = vec![0i32; n + 1];
    for i in 0..n { prefix[i+1] = prefix[i] + nums[i]; }
    let win = |l: usize, r: usize| prefix[r] - prefix[l];
    // max first..then second
    let mut res = 0i32;
    let mut max_first = 0i32;
    for i in (fl + sl)..=n {
      max_first = max_first.max(win(i - fl - sl, i - sl));
      res = res.max(max_first + win(i - sl, i));
    }
    // max second..then first
    let mut max_second = 0i32;
    for i in (fl + sl)..=n {
      max_second = max_second.max(win(i - fl - sl, i - fl));
      res = res.max(max_second + win(i - fl, i));
    }
    res
  }
}