Given an integer array nums, return the maximum possible sum of elements of the array such that it is divisible by three.
Example 1:
Input: nums = [3,6,5,1,8] Output: 18 Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).
Example 2:
Input: nums = [4] Output: 0 Explanation: Since 4 is not divisible by 3, do not pick any number.
Example 3:
Input: nums = [1,2,3,4,4] Output: 12 Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).
Constraints:
1 <= nums.length <= 4 * 1041 <= nums[i] <= 104Problem 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.
This approach uses dynamic programming to maintain the maximum sum with each possible remainder modulo 3. The idea is to track sums where the total sum % 3 == 0, 1, or 2, ensuring that the sum maximized at each step can correctly reach a state fully divisible by 3.
The solution maintains a dynamic programming table (an array of size 3) where each index represents the maximum sum possible with a remainder of 0, 1, and 2 respectively. We iterate over all numbers in the array and update our dp array to track the maximum possible sums with each remainder. At the end, we return dp[0], which is the maximum sum divisible by 3.
Time Complexity: O(n), where n is the number of elements in nums.
Space Complexity: O(1), due to the fixed size of the dp array.
This approach calculates the total sum of the array and modifies based on the remainder when divided by 3. If the total is not divisible by 3, it removes the smallest elements whose removal brings the sum to a number divisible by 3.
This solution calculates the total sum and handles adjustments based on the sum's remainder when divided by 3. If not divisible, we seek either a single number or two numbers whose effects upon removal yield divisibility by 3.
Time Complexity: O(n log n), due to sorting operations.
Space Complexity: O(n), for additional lists for tracking specific modulo groups.
We define f[i][j] as the maximum sum of several numbers selected from the first i numbers, such that the sum modulo 3 equals j. Initially, f[0][0]=0, and the rest are -infty.
For f[i][j], we can consider the state of the ith number x:
x, then f[i][j]=f[i-1][j];x, then f[i][j]=f[i-1][(j-x bmod 3 + 3)bmod 3]+x.Therefore, we can get the state transition equation:
$
f[i][j]=max{f[i-1][j],f[i-1][(j-x bmod 3 + 3)bmod 3]+x}
The final answer is f[n][0].
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.
Note that the value of f[i][j] is only related to f[i-1][j] and f[i-1][(j-x bmod 3 + 3)bmod 3], so we can use a rolling array to optimize the space complexity, reducing the space complexity to O(1)$.
Python
Java
C++
Go
TypeScript
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n), where n is the number of elements in nums. |
| Direct Modulo and Adjustment | Time Complexity: O(n log n), due to sorting operations. |
| Dynamic Programming | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Modulo States | O(n) | O(1) | General case when reasoning about remainders and subset sums |
| Direct Modulo Adjustment (Greedy) | O(n) | O(1) | When you recognize the remainder property and want a simpler implementation |
Greatest Sum Divisible by Three - Leetcode 1262 - Python • NeetCodeIO • 17,003 views views
Watch 9 more video solutions →Practice Greatest Sum Divisible by Three with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor