Maximum gcd sum of a subarray

Array Math Binary Search Number Theory

38.4% acceptance

Mar 31, 2026

You are given an array of integers nums and an integer k. The gcd-sum of an array a is calculated as follows: Let s be the sum of all the elements of a. Let g be the greatest common divisor of all the elements of a. The gcd-sum of a is equal to s * g. Return the maximum gcd-sum of a subarray of nums with at least k elements.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_gcd_sum(nums: Vec<i32>, k: i32) -> i64 {
    fn gcd(a: i64, b: i64) -> i64 {
      if b == 0 { a } else { gcd(b, a % b) }
    }
    let n = nums.len();
    let k = k as usize;
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + nums[i] as i64;
    }
    let mut ans = 0i64;
    let mut prev: Vec<(i64, usize)> = Vec::new();
    for i in 0..n {
      let mut curr: Vec<(i64, usize)> = vec![(nums[i] as i64, i)];
      for &(g, s) in &prev {
        let new_g = gcd(g, nums[i] as i64);
        if new_g != curr.last().unwrap().0 {
          curr.push((new_g, s));
        } else {
          curr.last_mut().unwrap().1 = s;
        }
      }
      for &(g, s) in &curr {
        if i + 1 - s >= k {
          ans = ans.max(g * (prefix[i + 1] - prefix[s]));
        }
      }
      prev = curr;
    }
    ans
  }
}