Given an integer array nums, find and return the maximum sum of elements that is divisible by three.

Examples

Example 1:

Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Choose numbers 3, 6, 1, and 8. Their sum is 18 (the maximum sum divisible by three).

Example 2:

Input: nums = [4]
Output: 0
Explanation: 4 is not divisible by 3, so no number can be chosen. Return 0.

Example 3:

Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Choose numbers 1, 3, 4, and 4. Their sum is 12 (the maximum sum divisible by three).

Constraints

• 1 <= nums.length <= 4 * 10^4
• 1 <= nums[i] <= 10^4

Solution Approaches

1. Recursive Backtracking (Inefficient)

An initial naive approach attempted recursion to find the maximum sum. However, this method is exponential and not feasible for large inputs.

var maxSumDivThree = function(nums) {
    let result; 
    arr = JSON.parse(JSON.stringify(nums));
    let find = (arr, nums)=>{
        if(!arr.length) return;
        let res = nums.reduce((a, b)=>a+b);
        if(!res%3){
            result = res;
            return
        } else {  
           let min =  Math.min(...nums);
            for(let i=0; i<nums.length; i++){
                if(min = nums[i]){
                    nums.splice(i, 1);
                    break;
                }
            }
            find(nums);
        }
    }
    for(let i=1; i<nums.length; i++){
      let res = find([], i, nums);
      if(res) break;
    }
    return result;
};

2. Dynamic Programming with Space Optimization

A more efficient DP approach uses two arrays of size 3 (for remainders 0, 1, 2) and processes each number, updating the maximum possible sum for each remainder. This uses O(1) extra space.

var maxSumDivThree = function(nums) {
    const max = [[0, 0, 0], [0, -1000000000, -1000000000]];
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < 3; j++) {
            max[i % 2][j] = Math.max(max[1 - i % 2][(3 + (j - nums[i]) % 3) % 3] + nums[i], max[1 - i % 2][j])
        }
    }
    return max[1 - nums.length % 2][0];
};

3. Dynamic Programming with Full Table

Another DP method stores the maximum sum for each remainder at every index, using a dp table of size 3 x n. It then returns the maximum value for remainder 0 across all indices.

var maxSumDivThree = function(nums) {
    const dp = []
    for (let i = 0; i < 3; i ++) {
        dp.push(new Array(nums.length).fill(-1))
    }
    dp[nums[0] % 3][0] = nums[0]
    for (let i = 1; i < nums.length; i ++) {
        dp[nums[i] % 3][i] = nums[i]
        for (let j = 0; j < 3; j ++) {
            if (dp[j][i - 1] != -1) {
                dp[j][i] = Math.max(dp[j][i], dp[j][i - 1])
            }
        }
        for (let j = 0; j < 3; j ++) {
            if (dp[j][i - 1] != -1) {
                dp[(j + nums[i]) % 3][i] = Math.max(dp[(j + nums[i]) % 3][i], dp[j][i - 1] + nums[i])
            }
        }
    }
    let res = 0
    for (let i = 0; i < nums.length; i ++) {
        if (dp[0][i] != -1) {
            res = Math.max(res, dp[0][i])
        }
    }
    return res
};