Greatest Sum Divisible by Three - Video Solutions

Problem Overview: You are given an integer array and need the maximum possible sum of elements such that the final sum is divisible by 3. You can choose any subset of elements. The challenge is maximizing the total while ensuring the remainder when divided by three equals zero.

Approach 1: Dynamic Programming with Modulo States (O(n) time, O(1) space)

This method tracks the best possible sums for each remainder when divided by three. Maintain a small DP array where dp[r] stores the maximum sum whose modulo with 3 equals r. For every number in the array, update the states by combining the current value with existing sums and adjusting the modulo using (oldRemainder + num) % 3. Only the largest sums for each remainder are kept. Since there are only three states (0, 1, 2), the memory footprint remains constant and updates are fast. This approach effectively builds the best divisible sum incrementally while scanning the array once.

Approach 2: Direct Modulo Adjustment (Greedy) (O(n) time, O(1) space)

Start by computing the total sum of all numbers. If the sum is already divisible by three, that value is the answer. Otherwise, remove the smallest elements necessary to fix the remainder. If the total remainder is 1, remove either one number with remainder 1 or two numbers with remainder 2. If the remainder is 2, remove either one number with remainder 2 or two numbers with remainder 1. Tracking the smallest candidates while iterating the array avoids sorting and keeps the solution linear. This approach uses a greedy observation about minimizing the removed sum to maximize the remaining divisible total.

The DP method is conceptually clean and aligns with problems involving remainder states, which commonly appear in dynamic programming. The greedy adjustment approach is slightly more intuitive once you recognize that only the modulo remainder matters.

Recommended for interviews: The dynamic programming solution is the safest explanation during interviews because it generalizes well to other remainder problems and demonstrates strong DP reasoning. The greedy modulo adjustment solution is equally optimal in O(n) time but relies on recognizing the mathematical property of divisibility by three. Showing the DP reasoning first and then mentioning the greedy optimization signals strong problem‑solving depth.