Maximum sum of 3 non overlapping subarrays

Array Dynamic Programming Sliding Window Prefix Sum

59.7% acceptance

Feb 20, 2026

2611

159

Find three non-overlapping subarrays of length k with maximum sum. Return lexicographically smallest indices.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_sum_of_three_subarrays(nums: Vec<i32>, k: i32) -> Vec<i32> {
    let n = nums.len();
    let k = k as usize;
    // Build window sums
    let mut sums = vec![0i32; n - k + 1];
    let mut s: i32 = nums[..k].iter().sum();
    sums[0] = s;
    for i in 1..=n - k {
      s += nums[i + k - 1] - nums[i - 1];
      sums[i] = s;
    }
    let m = sums.len();
    // left[i] = index of max sum in sums[0..=i]
    let mut left = vec![0usize; m];
    let mut best = 0usize;
    for i in 0..m {
      if sums[i] > sums[best] { best = i; }
      left[i] = best;
    }
    // right[i] = index of max sum in sums[i..m]
    let mut right = vec![0usize; m];
    best = m - 1;
    for i in (0..m).rev() {
      if sums[i] >= sums[best] { best = i; }
      right[i] = best;
    }
    let mut ans = vec![-1i32; 3];
    let mut max_sum = 0i32;
    for j in k..m - k {
      let l = left[j - k];
      let r = right[j + k];
      let total = sums[l] + sums[j] + sums[r];
      if total > max_sum {
        max_sum = total;
        ans = vec![l as i32, j as i32, r as i32];
      }
    }
    ans
  }
}