Greatest Sum Divisible by Three

medium dynamic programming modular arithmetic array

Problem

Given an integer array nums, return the maximum possible sum of a subset of its elements such that the sum is divisible by three. You may pick any subset (including the empty one, whose sum is 0).

Inputnums = [3,6,5,1,8]

Output18

Pick 3, 6, 1 and 8 — their sum 18 is the largest total divisible by 3.

Inputnums = [1,2,3,4,4]

Output12

Pick 1, 3, 4 and 4 — their sum is 12, the maximum divisible by 3.

nums (comma-separated)

def max_sum_div_three(nums):
    NEG = float("-inf")
    dp = [0, NEG, NEG]          # dp[r] = best sum with sum % 3 == r
    for v in nums:
        cur = dp[:]             # snapshot before using v
        for r in range(3):
            if cur[r] == NEG:
                continue
            nr = (cur[r] + v) % 3
            dp[nr] = max(dp[nr], cur[r] + v)
    return dp[0]

function maxSumDivThree(nums) {
  const NEG = -Infinity;
  let dp = [0, NEG, NEG];        // dp[r] = best sum with sum % 3 === r
  for (const v of nums) {
    const cur = dp.slice();      // snapshot before using v
    for (let r = 0; r < 3; r++) {
      if (cur[r] === NEG) continue;
      const nr = (cur[r] + v) % 3;
      dp[nr] = Math.max(dp[nr], cur[r] + v);
    }
  }
  return dp[0];
}

int maxSumDivThree(int[] nums) {
    final int NEG = Integer.MIN_VALUE;
    int[] dp = {0, NEG, NEG};      // dp[r] = best sum with sum % 3 == r
    for (int v : nums) {
        int[] cur = dp.clone();    // snapshot before using v
        for (int r = 0; r < 3; r++) {
            if (cur[r] == NEG) continue;
            int nr = (cur[r] + v) % 3;
            dp[nr] = Math.max(dp[nr], cur[r] + v);
        }
    }
    return dp[0];
}

int maxSumDivThree(vector<int>& nums) {
    const int NEG = INT_MIN;
    vector<int> dp = {0, NEG, NEG};   // dp[r] = best sum, sum % 3 == r
    for (int v : nums) {
        vector<int> cur = dp;         // snapshot before using v
        for (int r = 0; r < 3; r++) {
            if (cur[r] == NEG) continue;
            int nr = (cur[r] + v) % 3;
            dp[nr] = max(dp[nr], cur[r] + v);
        }
    }
    return dp[0];
}

Explanation

We never need to know which elements form a sum — only the sum's remainder modulo three. So we keep a tiny table dp of just three buckets: dp[r] holds the largest achievable sum whose value is congruent to r (mod 3) using the elements seen so far.

Start with dp = [0, -∞, -∞]: a sum of 0 is divisible by 3, while remainders 1 and 2 are not yet reachable (marked -∞).

For each new value v we first take a snapshot cur of the table, then for every reachable remainder r we consider adding v. The extended sum cur[r] + v lands in bucket nr = (cur[r] + v) % 3, so we relax dp[nr] = max(dp[nr], cur[r] + v). The snapshot prevents v from being counted twice within one round.

Because adding a fixed v rotates remainders predictably, every subset's sum is represented by exactly one bucket, and each bucket always stores the best total for its class.

After processing all elements, dp[0] is the maximum sum divisible by three (it can never drop below 0 because the empty subset seeds it). The whole table is constant size, so the work is linear in the array length.

Time: O(n) Space: O(1)