DSA problem
Greatest Sum Divisible by Three
Given an integer array nums, return the maximum possible sum of elements of the array such that it is divisible by three.
This is an elegant 1-D DP with a tiny state space. The key insight is that the only information we need about a "running sum so far" is its value modulo 3 — there are exactly three possible residues, so we can track the best achievable sum for each residue.
Define dp[r] to be the maximum sum we can build whose value is congruent to r (mod 3). Initially dp[0] = 0 (empty sum) and dp[1] = dp[2] = -infinity (no element seen yet that gives those residues).
For each n in nums, every existing residue class r can be extended by including n, producing a new sum with residue (r + n) % 3. The update is therefore: new_dp[(r + n) % 3] = max(dp[(r + n) % 3], dp[r] + n) for all r. To avoid using the just-updated values inside the same iteration, snapshot dp into a local copy before applying the three updates.
After processing the entire array, dp[0] is the answer: the largest sum whose value mod 3 is zero. The whole algorithm is O(n) time and O(1) space.
Examples
nums = [3,6,5,1,8]18nums = [4]0nums = [1,2,3,4,4]12Constraints
- 1 <= nums.length <= 4 * 10^4
- 1 <= nums[i] <= 10^4
- The empty subset is allowed (sum 0 is divisible by 3).
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.