Greatest Sum Divisible by Three: Remainder DP Pattern

Given an array of integers nums, find the maximum possible sum of elements such that the sum is divisible by 3.

This is LeetCode 1262: Greatest Sum Divisible by Three, and it teaches one of the most elegant DP patterns out there: tracking remainders as your DP state. Instead of building a table indexed by every possible sum, you only need three slots, one for each remainder when dividing by 3. That compression from potentially huge state space down to three values is what makes this problem so satisfying.

Why this problem matters

Most DP problems define their state around indices, amounts, or lengths. This one introduces a different idea: modular arithmetic as DP state. You track the best achievable sum for each remainder class (0, 1, and 2), and when you process a new number, you update all three classes based on what adding that number does to the remainder.

This pattern generalizes well. Any time you see a constraint like "divisible by k" or "remainder equals r," the same approach applies. You maintain k states instead of 3, and the transitions use modular addition. Once you internalize this building block, problems like Subarray Sums Divisible by K and similar divisibility challenges become much more approachable.

The approach

The key insight is that you do not need to track which elements you picked. You only need to know, for each possible remainder (0, 1, 2), what is the largest sum you can achieve with that remainder.

Define dp[r] as the maximum sum achievable so far where sum % 3 == r. Initialize dp[0] = 0 (the empty subset has sum 0, which is divisible by 3) and dp[1] = dp[2] = -infinity (no valid sums exist yet for those remainders).

For each number in the array, you create a temporary copy of the current DP state and then update. If the current number has remainder rem, then adding it to an existing sum with remainder r produces a new sum with remainder (r + rem) % 3. You take the max of the old value and the new candidate for each slot.

After processing every element, dp[0] holds the answer: the maximum sum whose remainder when divided by 3 is zero.

The solution

def maxSumDivThree(nums):
    dp = [0, float('-inf'), float('-inf')]

    for num in nums:
        temp = dp[:]
        for r in range(3):
            new_r = (r + num % 3) % 3
            dp[new_r] = max(dp[new_r], temp[r] + num)

    return dp[0]

The outer loop iterates through each number once. The inner loop always runs exactly 3 times, regardless of the input size. We copy the DP array into temp before updating so that we do not use values from the current iteration when computing transitions, which would let an element be counted multiple times in a single step.

The key line is new_r = (r + num % 3) % 3. This calculates what the remainder becomes after adding the current number to a sum that already has remainder r. Then we check whether this new sum is better than what we previously had for that remainder slot.

Visual walkthrough

Notice how the DP state only has 3 values at any point. Even though the array [3, 6, 5, 1, 8] sums to 23, we never need to track sums up to 23. We just track the best sum for each of the three remainder classes. The answer is dp[0] = 18, achieved by picking 3 + 6 + 1 + 8 = 18.

Complexity analysis

The time complexity is O(n) because we process each element once with a constant-time inner loop of size 3. The space complexity is O(1) because the DP array always has exactly 3 entries, regardless of how large the input is. The temporary copy temp is also size 3. No auxiliary data structures grow with the input.

The building blocks

1. Remainder-based state tracking

The fundamental insight is compressing an enormous state space into a tiny one. Instead of asking "what is the maximum sum I can make from this subset?" (which could be exponentially many subsets), you ask "what is the maximum sum I can make that has remainder 0? remainder 1? remainder 2?" Three values capture everything you need.

dp = [0, float('-inf'), float('-inf')]

This initialization says: the empty subset has sum 0 (remainder 0 is valid), and no subset yet produces a sum with remainder 1 or 2. Using negative infinity rather than zero is critical. Zero would falsely claim that a sum with remainder 1 already exists. Negative infinity correctly propagates through the max comparisons until a real sum replaces it.

2. DP transition with modular arithmetic

When you add a number with remainder rem to a sum with remainder r, the new remainder is (r + rem) % 3. This is the transition rule that drives the entire algorithm.

for r in range(3):
    new_r = (r + num % 3) % 3
    dp[new_r] = max(dp[new_r], temp[r] + num)

The copy into temp is necessary to prevent "double-counting" within one step. Without it, updating dp[0] first could affect the computation of dp[1] or dp[2] within the same element, which would be incorrect. Each element should only be added once per transition.

Edge cases

• All elements divisible by 3: every element has remainder 0, so the answer is the sum of the entire array.
• No subset divisible by 3: this cannot happen because the empty subset has sum 0, which is divisible by 3. The minimum answer is always 0.
• Single element: if nums = [4], then 4 % 3 = 1, so the best sum divisible by 3 is 0 (we skip the element). If nums = [3], the answer is 3.
• All elements have the same remainder: for example, [1, 4, 7] all have remainder 1. You need to pick three of them (or zero) for a sum divisible by 3. Picking all three gives 1 + 4 + 7 = 12.
• Large input: the constraints allow up to 40,000 elements with values up to 10,000. The O(n) time and O(1) space solution handles this comfortably.

From understanding to recall

Reading through this walkthrough, you can probably trace the DP transitions for any example. But will you remember the initialization trick with negative infinity next week? Will you recall why the temp copy is needed instead of updating in place?

Understanding and recall are different skills. Spaced repetition closes the gap. You revisit the remainder DP pattern at increasing intervals, write the three-state transition from scratch each time, and after a few reps the modular arithmetic approach becomes automatic. No more second-guessing whether (r + rem) % 3 gives you the right slot.

The remainder-based DP pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Related posts

• Coin Change - Classic DP with a target constraint
• Partition Equal Subset Sum - DP with a sum-based constraint
• Subarray Sums Divisible by K - Another modular arithmetic pattern

CodeBricks organizes problems by the underlying building blocks they test, so you practice the remainder DP pattern across multiple problems rather than seeing it once and forgetting it. Each rep strengthens the connection between the problem type and the solution shape.