Problem Description

You are given an integer array nums. Your task is to find the maximum possible sum of elements from the array such that this sum is divisible by three.

You can select any subset of numbers from the array (including selecting all numbers or selecting none). The goal is to maximize the sum while ensuring that the total sum, when divided by 3, gives a remainder of 0.

For example:

• If nums = [3, 6, 5, 1, 8], you could select [3, 6] for a sum of 9 (divisible by 3), or [3, 6, 1, 8] for a sum of 18 (also divisible by 3). The maximum sum divisible by 3 would be 18.
• If no combination of numbers can form a sum divisible by 3, and you cannot select any numbers to get 0, then return 0.

The problem requires finding the optimal selection of array elements to achieve the largest sum that satisfies the divisibility constraint.

Intuition

When we need to find a sum divisible by 3, we need to think about remainders. Any number, when divided by 3, gives a remainder of 0, 1, or 2. The key insight is that the remainder of a sum depends only on the remainders of its parts.

For example, if we have numbers with remainders 1 and 2, their sum has remainder (1 + 2) % 3 = 0. This means we can track the maximum possible sum for each remainder value (0, 1, or 2) as we process the array.

Think of it this way: as we go through each number in the array, we have three "buckets" representing the maximum sums we can achieve with remainders 0, 1, and 2. For each new number, we can either:

1. Skip it - keeping our current bucket values unchanged
2. Add it to one of our existing sums - which might change which remainder bucket the sum belongs to

When we add a number x to a sum that has remainder j, the new sum will have remainder (j + x) % 3. So if we want to achieve remainder j, we could have taken a previous sum with remainder (j - x) % 3 and added x to it.

This naturally leads to a dynamic programming approach where we track:

• f[i][j] = maximum sum using numbers from the first i elements, where the sum has remainder j when divided by 3

We build up our answer by considering each number one by one, updating our three remainder buckets, and finally returning the maximum sum with remainder 0, which is f[n][0].

Learn more about Greedy, Dynamic Programming and Sorting patterns.

Solution Approach

We implement the dynamic programming solution using a 2D array f where f[i][j] represents the maximum sum we can achieve using the first i numbers such that the sum modulo 3 equals j.

Initialization:

• Create a 2D array f of size (n+1) × 3, where n is the length of the input array
• Initialize all values to -inf (negative infinity) to represent impossible states
• Set f[0][0] = 0 because with 0 numbers selected, we can achieve a sum of 0 (which has remainder 0)

State Transition: For each number x at position i (1-indexed), we update all three remainder states:

f[i][j] = max(f[i-1][j], f[i-1][(j-x) % 3] + x)

This formula means:

• f[i-1][j]: Don't include the current number x, keep the maximum sum with remainder j from previous numbers
• f[i-1][(j-x) % 3] + x: Include the current number x. To get remainder j after adding x, we need the previous sum to have remainder (j-x) % 3

Implementation Details:

1. We iterate through each number in the array using enumerate(nums, 1) to get 1-indexed positions
2. For each position i and each possible remainder j (0, 1, 2), we calculate the maximum between:
   • Not taking the current number
   • Taking the current number and adding it to a previous sum

Computing the Previous Remainder: The expression (j - x) % 3 in Python handles negative numbers correctly. For example:

• If j = 0 and x = 2, then (0 - 2) % 3 = 1 in Python
• This means to get remainder 0 after adding a number with remainder 2, we need a previous sum with remainder 1

Final Answer: After processing all numbers, f[n][0] gives us the maximum sum that is divisible by 3 (remainder 0).

The time complexity is O(n) since we iterate through each number once and perform constant operations for each of the 3 remainder states. The space complexity is O(n) for the 2D DP array.

Example Walkthrough

Let's walk through the solution with nums = [3, 6, 5, 1, 8].

We'll build a DP table f[i][j] where i represents using the first i numbers, and j represents the remainder when the sum is divided by 3.

Initial Setup:

• Initialize f[0][0] = 0 (sum of 0 has remainder 0)
• Initialize f[0][1] = -inf and f[0][2] = -inf (impossible to have non-zero remainders with no numbers)

Processing each number:

Step 1: Process 3 (remainder = 0)

• For remainder 0: f[1][0] = max(f[0][0], f[0][(0-3)%3] + 3) = max(0, f[0][0] + 3) = max(0, 3) = 3
• For remainder 1: f[1][1] = max(f[0][1], f[0][(1-3)%3] + 3) = max(-inf, f[0][1] + 3) = max(-inf, -inf) = -inf
• For remainder 2: f[1][2] = max(f[0][2], f[0][(2-3)%3] + 3) = max(-inf, f[0][2] + 3) = max(-inf, -inf) = -inf

Step 2: Process 6 (remainder = 0)

• For remainder 0: f[2][0] = max(f[1][0], f[1][(0-6)%3] + 6) = max(3, f[1][0] + 6) = max(3, 9) = 9
• For remainder 1: f[2][1] = max(f[1][1], f[1][(1-6)%3] + 6) = max(-inf, f[1][1] + 6) = -inf
• For remainder 2: f[2][2] = max(f[1][2], f[1][(2-6)%3] + 6) = max(-inf, f[1][2] + 6) = -inf

Step 3: Process 5 (remainder = 2)

• For remainder 0: f[3][0] = max(f[2][0], f[2][(0-5)%3] + 5) = max(9, f[2][1] + 5) = max(9, -inf) = 9
• For remainder 1: f[3][1] = max(f[2][1], f[2][(1-5)%3] + 5) = max(-inf, f[2][2] + 5) = -inf
• For remainder 2: f[3][2] = max(f[2][2], f[2][(2-5)%3] + 5) = max(-inf, f[2][0] + 5) = max(-inf, 14) = 14

Step 4: Process 1 (remainder = 1)

• For remainder 0: f[4][0] = max(f[3][0], f[3][(0-1)%3] + 1) = max(9, f[3][2] + 1) = max(9, 15) = 15
• For remainder 1: f[4][1] = max(f[3][1], f[3][(1-1)%3] + 1) = max(-inf, f[3][0] + 1) = max(-inf, 10) = 10
• For remainder 2: f[4][2] = max(f[3][2], f[3][(2-1)%3] + 1) = max(14, f[3][1] + 1) = max(14, -inf) = 14

Step 5: Process 8 (remainder = 2)

• For remainder 0: f[5][0] = max(f[4][0], f[4][(0-8)%3] + 8) = max(15, f[4][1] + 8) = max(15, 18) = 18
• For remainder 1: f[5][1] = max(f[4][1], f[4][(1-8)%3] + 8) = max(10, f[4][2] + 8) = max(10, 22) = 22
• For remainder 2: f[5][2] = max(f[4][2], f[4][(2-8)%3] + 8) = max(14, f[4][0] + 8) = max(14, 23) = 23

Final Answer: f[5][0] = 18, which represents the maximum sum divisible by 3.

This corresponds to selecting [3, 6, 1, 8] which sum to 18.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input array nums. The algorithm uses two nested loops - the outer loop iterates through all n elements, and the inner loop iterates exactly 3 times for each element (constant factor). Therefore, the overall time complexity is O(n × 3) = O(n).

Space Complexity: O(n). The code creates a 2D array f with dimensions (n+1) × 3, which requires O(n) space. According to the reference answer, since f[i][j] only depends on f[i-1][j] and f[i-1][(j-x) % 3] from the previous row, we could optimize this to use a rolling array approach with only two rows or even a single row with careful updates, reducing the space complexity to O(1) (constant space for storing just 3 values for the current and previous states).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Impossible States

The Pitfall: A common mistake is initializing the DP table with 0s instead of negative infinity. This leads to incorrect results because 0 is a valid sum, and using it as a placeholder for "impossible" states causes the algorithm to consider invalid transitions.

# WRONG: Initializing with zeros
dp = [[0] * 3 for _ in range(n + 1)]
dp[0][0] = 0  # This looks correct but...

Why it's wrong: When we have dp[0][1] = 0 and dp[0][2] = 0, the algorithm thinks we can achieve sums with remainders 1 and 2 using zero elements, which is impossible. This leads to incorrect state transitions when including numbers.

The Solution:

# CORRECT: Initialize with negative infinity for impossible states
dp = [[-float('inf')] * 3 for _ in range(n + 1)]
dp[0][0] = 0  # Only this state is possible initially

2. Space Optimization Without Proper State Copying

The Pitfall: When optimizing space to use only two 1D arrays (or even one), developers often forget to properly copy states between iterations:

# WRONG: Modifying the same array in-place
dp = [-float('inf')] * 3
dp[0] = 0
for num in nums:
    for j in range(3):
        prev_remainder = (j - num) % 3
        dp[j] = max(dp[j], dp[prev_remainder] + num)  # Bug: dp[prev_remainder] might be already updated!

Why it's wrong: When updating dp[j] in the same array, we might use values that have already been updated in the current iteration, breaking the DP logic.

The Solution:

# CORRECT: Use a temporary array or process in reverse order
dp = [-float('inf')] * 3
dp[0] = 0
for num in nums:
    new_dp = dp.copy()  # Create a copy for the new state
    for j in range(3):
        prev_remainder = (j - num) % 3
        new_dp[j] = max(dp[j], dp[prev_remainder] + num)
    dp = new_dp

3. Modulo Operation Confusion with Negative Numbers

The Pitfall: In some programming languages, the modulo operation with negative numbers behaves differently. Developers might write:

# Potentially problematic in other languages
prev_remainder = (j - current_num) % 3

Why it could be wrong: In languages like Java or C++, -1 % 3 returns -1, not 2 as in Python. This would require additional handling.

The Solution for other languages:

# Universal solution that works in all languages
prev_remainder = ((j - current_num) % 3 + 3) % 3

This ensures the result is always in the range [0, 2] regardless of the language's modulo implementation.