# 1262. Greatest Sum Divisible by Three

[Link](https://leetcode.com/problems/greatest-sum-divisible-by-three/)

Given an array `nums` of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.

1.

**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).
```

**Constraints:**

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

#### Solution

```java
    public int maxSumDivThree(int[] A) {
        //dp[0] : the max sum which %3==0, shall be init by 0, no select so far
        //dp[1] : the max sum which %3==1, not existed, Integer.MIN_VALUE
        //dp[2] : the max sum which %3==2, not existed, Integer.MIN_VALUE
        
        int[] dp = {0, Integer.MIN_VALUE, Integer.MIN_VALUE};
        
        for(int num : A){
            //for each num in A, consider it's impact on the dp, 
            // and save new resulting dp to temp
            int[] temp = new int[3];
            for(int i = 0; i < 3; i++){
                //not take num, temp[(i+num)%3] = dp[(i+num)%3], reuse previoud      
                //take it 
                temp[(i+num)%3] = Math.max(dp[(i+num)%3], num + dp[i]);
            }
            dp = temp;
        }
        return dp[0];
    }
```
