1262. Greatest Sum Divisible by Three

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

Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.

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

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][0]
    }
}

#[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![4];
    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);
}