Maximum good subarray sum

Array Hash Table Prefix Sum

21.4% acceptance

Feb 25, 2026

477

You are given an array nums of length n and a positive integer k. A subarray of nums is called good if the absolute difference between its first and last element is exactly k, in other words, the subarray nums[i..j] is good if |nums[i] - nums[j]| == k. Return the maximum sum of a good subarray of nums. If there are no good subarrays, return 0.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_subarray_sum(nums: Vec<i32>, k: i32) -> i64 {
    use std::collections::HashMap;
    let n = nums.len();
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n { prefix[i+1] = prefix[i] + nums[i] as i64; }
    // For each j, find i with |nums[i] - nums[j]| == k and maximize prefix[j+1] - prefix[i]
    // = prefix[j+1] - min(prefix[i]) for valid i
    let mut min_prefix: HashMap<i32, i64> = HashMap::new();
    let mut ans = i64::MIN;
    for j in 0..n {
      let v = nums[j];
      for &target in &[v - k, v + k] {
        if let Some(&mp) = min_prefix.get(&target) {
          let s = prefix[j+1] - mp;
          if ans == i64::MIN || s > ans { ans = s; }
        }
      }
      let e = min_prefix.entry(v).or_insert(i64::MAX);
      *e = (*e).min(prefix[j]);
    }
    if ans == i64::MIN { 0 } else { ans }
  }
}