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^41 <= nums[i] <= 10^4struct 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);
}