## 1262. 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.

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 = 
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`

## Rust Solution

``````struct Solution;

impl Solution {
fn max_sum_div_three(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut dp = vec![vec![0; 3]; 2];
for i in 0..n {
for j in 0..3 {
dp[(i + 1) % 2][j] = dp[(i + 1) % 2][j].max(dp[i % 2][j]);
let sum = dp[i % 2][j] + nums[i];
let sum_mod_3 = (sum % 3) as usize;
dp[(i + 1) % 2][sum_mod_3] = dp[(i + 1) % 2][sum_mod_3].max(sum);
}
}
dp[n % 2]
}
}

#[test]
fn test() {
let nums = vec![3, 6, 5, 1, 8];
let res = 18;
assert_eq!(Solution::max_sum_div_three(nums), res);
let nums = vec!;
let res = 0;
assert_eq!(Solution::max_sum_div_three(nums), res);
let nums = vec![1, 2, 3, 4, 4];
let res = 12;
assert_eq!(Solution::max_sum_div_three(nums), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.