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

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);
}

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