Code Implementation

class Solution:
    def maxSumDivThree(self, nums):
        dp = [0, float('-inf'), float('-inf')]
        for num in nums:
            temp = dp[:]
            for i in range(3):
                new_mod = (i + num) % 3
                temp[new_mod] = max(temp[new_mod], dp[i] + num)
            dp = temp
        return dp[0]
    

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        vector<int> dp = {0, INT_MIN, INT_MIN};
        for (int num : nums) {
            vector<int> temp = dp;
            for (int i = 0; i < 3; ++i) {
                int new_mod = (i + num) % 3;
                temp[new_mod] = max(temp[new_mod], dp[i] + num);
            }
            dp = temp;
        }
        return dp[0];
    }
};
    

class Solution {
    public int maxSumDivThree(int[] nums) {
        int[] dp = {0, Integer.MIN_VALUE, Integer.MIN_VALUE};
        for (int num : nums) {
            int[] temp = dp.clone();
            for (int i = 0; i < 3; ++i) {
                int newMod = (i + num) % 3;
                temp[newMod] = Math.max(temp[newMod], dp[i] + num);
            }
            dp = temp;
        }
        return dp[0];
    }
}
    

var maxSumDivThree = function(nums) {
    let dp = [0, -Infinity, -Infinity];
    for (let num of nums) {
        let temp = dp.slice();
        for (let i = 0; i < 3; ++i) {
            let newMod = (i + num) % 3;
            temp[newMod] = Math.max(temp[newMod], dp[i] + num);
        }
        dp = temp;
    }
    return dp[0];
};
    

Problem Description

You are given an array of integers called nums. Your task is to find the greatest possible sum of some (possibly all or none) elements of nums such that the sum is divisible by 3.

You may choose any subset of elements from nums, but you cannot reuse elements. The answer should be the maximum sum that is divisible by 3. If no such sum exists, return 0.

Key Constraints:

• Each element in nums can be used at most once.
• There is always at least one valid solution (possibly the empty subset).
• Array length is up to 4 × 10⁴; each element is between 1 and 10⁴.

Thought Process

The first idea is to try all possible subsets and check which ones sum to a number divisible by 3, keeping track of the largest such sum. However, this "brute-force" approach is not practical for large arrays, since the number of subsets grows exponentially (2ⁿ).

To optimize, we notice that the only thing that matters about the sum is its remainder when divided by 3. So, instead of tracking every possible sum, we can track the best sums for each possible remainder (0, 1, or 2). This is a classic dynamic programming (DP) scenario: at each step, we update our best possible sum for each remainder as we process each number.

The main insight is that for each number, we can try adding it to each current "best sum" for each remainder, and see if that leads to a better sum for the new remainder.

Solution Approach

• Step 1: Initialize a DP array with three elements: dp[0], dp[1], dp[2]. Each entry will track the maximum sum we can achieve so far with a sum whose remainder modulo 3 is 0, 1, or 2, respectively. Initially, dp[0]=0 (using no elements), and dp[1]=dp[2]=-∞ (impossible to get these remainders yet).
• Step 2: For each number in nums, make a copy of the current DP array (since we'll update all three entries for this number).
• Step 3: For each possible current remainder (i from 0 to 2), try adding the current number to the sum for that remainder. The new sum's remainder will be (i + num) % 3. Update the DP entry for that new remainder if this sum is better.
• Step 4: After processing all numbers, dp[0] contains the largest sum divisible by 3.

This approach works because at each step, we only care about the best possible sum for each possible remainder, and we always keep these up to date.

Example Walkthrough

Let's use the input nums = [3, 6, 5, 1, 8].

• Start: dp = [0, -∞, -∞]
• Process 3:
  • Add 3 to dp[0] (0): (0+3)%3=0, so dp[0]=max(0, 0+3)=3
  • dp = [3, -∞, -∞]
• Process 6:
  • Add 6 to dp[0] (3): (0+6)%3=0, so dp[0]=max(3, 3+6)=9
  • dp = [9, -∞, -∞]
• Process 5:
  • Add 5 to dp[0] (9): (0+5)%3=2, so dp[2]=max(-∞, 9+5)=14
  • dp = [9, -∞, 14]
• Process 1:
  • Add 1 to dp[0] (9): (0+1)%3=1, so dp[1]=max(-∞, 9+1)=10
  • Add 1 to dp[2] (14): (2+1)%3=0, so dp[0]=max(9, 14+1)=15
  • dp = [15, 10, 14]
• Process 8:
  • Add 8 to dp[0] (15): (0+8)%3=2, so dp[2]=max(14, 15+8)=23
  • Add 8 to dp[1] (10): (1+8)%3=0, so dp[0]=max(15, 10+8)=18
  • Add 8 to dp[2] (14): (2+8)%3=0, so dp[0]=max(18, 14+8)=22
  • Final dp = [22, 10, 23]

The answer is 22, the largest sum divisible by 3.

Time and Space Complexity

Brute-force approach: Would consider all 2ⁿ subsets, which is infeasible for large n.

Optimized DP approach:

• Time Complexity: O(n), where n is the length of nums. For each number, we do a constant amount of work (3 updates).
• Space Complexity: O(1), since we only track 3 values in the DP array, regardless of input size.

This makes the solution very efficient, even for large input arrays.

Summary

By recognizing that only the remainder modulo 3 matters, we avoid brute-force and use a compact dynamic programming approach. We keep track of the best possible sum for each remainder, updating as we process each number. This results in an elegant, efficient solution that runs in linear time and constant space, suitable for large input sizes.