Greatest Sum Divisible by Three - Solution & Explanation

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.

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.