Leetcode•Oct 24, 2026
Greatest Sum Divisible by Three
Hazrat Ali
Leetcode
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).
Solution
var maxSumDivThree = function(nums) {
let dp = [0, -Infinity, -Infinity];
for (const num of nums) {
const prev = [...dp];
for (let r = 0; r < 3; r++) {
if (prev[r] !== -Infinity) {
const sum = prev[r] + num;
const remainder = sum % 3;
dp[remainder] = Math.max(dp[remainder], sum);
}
}
}
return dp[0];
};