We want the largest subset sum that is divisible by 3. Adding every element gives the largest possible sum, but that total might not be divisible by 3. When it is not, we have to drop some elements to fix the remainder while sacrificing as little as possible.

This reduces to working with remainders mod 3. Every number leaves a remainder of 0, 1, or 2 when divided by 3, and so does the total sum. If the total has remainder 0, it is already the answer. If the total has remainder 1, we restore divisibility by removing either the smallest element with remainder 1, or the two smallest elements with remainder 2 (because 2 + 2 = 4 has remainder 1). If the total has remainder 2, we remove either the smallest remainder-2 element or the two smallest remainder-1 elements. That is the greedy approach.

A dynamic programming approach avoids the removal logic entirely by tracking the best achievable sum for each remainder (0, 1, 2) as it processes each number in one pass.

Key Constraints:

Intuition

Add up all the numbers. If the total is already divisible by 3, that total is the answer. Otherwise we remove the elements that subtract the least while fixing the remainder.

The remainder of the total is either 1 or 2. When it is 1, two removals restore divisibility: dropping the single smallest remainder-1 element, or dropping the two smallest remainder-2 elements (since 2 + 2 = 4 and 4 mod 3 = 1). We pick whichever subtracts less. When the remainder is 2, the symmetric options are the smallest remainder-2 element or the two smallest remainder-1 elements.

Why are only these two options worth checking for remainder 1? To lower a sum with remainder 1 down to remainder 0, the removed elements must themselves sum to a remainder of 1. The cheapest ways to reach remainder 1 are one remainder-1 element or two remainder-2 elements. Any other combination removes at least as much, so the minimum is one of these two. Sorting puts the smallest element of each remainder class at the front, so we read them directly.

Algorithm

Example Walkthrough

Input:

Total sum = 23, remainder = 23 % 3 = 2. We need to remove the minimum to fix this.

After sorting: [1, 3, 5, 6, 8]. Remainder-2 elements (sorted): [5, 8]. Remainder-1 elements (sorted): [1].

Option A: Remove smallest remainder-2 element (5), sum = 23 - 5 = 18.

Option B: Remove two smallest remainder-1 elements, but only one exists. Not possible.

Best option: 18.

Code

The greedy approach needs a sort and extra lists for the remainder classes. The next approach removes both by tracking the best sum for each remainder in a single pass.

Intuition

Instead of computing the total and then removing elements, we build the answer incrementally while keeping only three numbers: the maximum sum reachable so far with remainder 0, with remainder 1, and with remainder 2.

For each new number we choose to include it or skip it. Including it adds the number to one of the existing sums and shifts that sum into a new remainder class. If the best sum with remainder 1 is 10 and the new number has remainder 2, then 10 plus that number has remainder 0 (1 + 2 = 3). So a remainder-2 number can improve dp[0] by building on the current dp[1].

We hold an array dp of size 3, where dp[r] is the maximum sum whose value mod 3 equals r. We start with dp[0] = 0 (the empty subset has sum 0, remainder 0) and dp[1] = dp[2] = -infinity, marking those remainders as unreachable until some element produces them. Each number updates all three states from a snapshot of the previous values.

Algorithm

Example Walkthrough

Code