Greatest sum divisible by three

Array Dynamic Programming Greedy Sorting

57.1% acceptance

Feb 25, 2026

2413

Given an integer array nums, return the maximum possible sum of elements of the array such that it is divisible by three.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_sum_div_three(nums: Vec<i32>) -> i32 {
    // dp[r] = max sum with remainder r when divided by 3
    let mut dp = [0i32, i32::MIN / 2, i32::MIN / 2];

    for &x in &nums {
      let prev = dp;
      for r in 0..3 {
        let new_r = (r + (x % 3) as usize) % 3;
        if prev[r] > i32::MIN / 2 {
          dp[new_r] = dp[new_r].max(prev[r] + x);
        }
      }
    }
    dp[0].max(0)
  }
}