Given an integer array nums, return the maximum possible sum of elements of the array such that it is divisible by three.

&nbsp;
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).


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 4 * 10^4
	1 &lt;= nums[i] &lt;= 10^4


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dp = [0, float('-inf'), float('-inf')]
        for x in nums:
            dp_cp = dp[:]
            for left in range(3):
                right = (left + x) % 3
                dp[right] = max(dp_cp[right], dp_cp[left] + x)

        return dp[0]
class Solution {

    public int maxSumDivThree(int[] nums) {
        int r0 = 0;
        int r1 = 0;
        int r2 = 0;
        for (int i = 0; i < nums.length; i++) {
            int nr0 = r0;
            int nr1 = r1;
            int nr2 = r2;
            int a = r0 + nums[i];
            int b = r1 + nums[i];
            int c = r2 + nums[i];
            if (a % 3 == 0) {
                nr0 = Math.max(nr0, a);
            } else if (a % 3 == 1) {
                nr1 = Math.max(nr1, a);
            } else if (a % 3 == 2) {
                nr2 = Math.max(nr2, a);
            }

            if (b % 3 == 0) {
                nr0 = Math.max(nr0, b);
            } else if (b % 3 == 1) {
                nr1 = Math.max(nr1, b);
            } else if (b % 3 == 2) {
                nr2 = Math.max(nr2, b);
            }

            if (c % 3 == 0) {
                nr0 = Math.max(nr0, c);
            } else if (c % 3 == 1) {
                nr1 = Math.max(nr1, c);
            } else if (c % 3 == 2) {
                nr2 = Math.max(nr2, c);
            }
            r0=nr0;
            r1=nr1;
            r2=nr2;
        }

        return r0;
    }
}
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        vector<int> twos = {(int)1e4+1, (int)1e4+1}, ones = {(int)1e4+1, (int)1e4+1};
        int res = 0;
        for(int i: nums) {
            if(i%3 == 2) {
                if(i <= twos[0]) {
                    twos[1] = twos[0], twos[0] = i;
                }
                else if(i < twos[1]) twos[1] = i;
            }
            else if(i%3 == 1) {
                if(i <= ones[0]) {
                    ones[1] = ones[0], ones[0] = i;
                }
                else if(i < ones[1]) ones[1] = i;
            }
            res += i;
        }
        if(res%3 == 2)
            return max(res - twos[0], res - ones[0] - ones[1]);
        else if(res%3 == 1)
            return max(res - ones[0], res - twos[0] - twos[1]);
        return res;
    }
};
var maxSumDivThree = function(nums) {
    // there are 3 options for how the sum fit's into 3 via mod % 3
    // track those 3 options via indices in the dp array
    // dp[0] = %3 === 0
    // dp[1] = %3 === 1
    // dp[2] = %3 === 2
    let dp = new Array(3).fill(0);
    for (let num of nums) {
        for (let i of dp.slice(0)) {
            let sum = i + num;
            let mod = sum % 3;
            // on each pass, set the value of dp[mod] to the Math.max val
            dp[mod] = Math.max(dp[mod], sum);
        }
    }
    return dp[0];
};
Greatest Sum Divisible by Three