problem

Given an integer array nums, return 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 * 104
  • 1 <= nums[i] <= 104

submission

// stateful dynamic programming
// use dp[pos][mod] to denote max possible sum of subslice [0..=pos]
// to satisify `dp[pos][mod] % 3 == mod`
// the transition here is a bit mess to write down but should be
// fairly easy to think or reason about.
// and our init state should be (0, -inf, -inf), since the only
// possible sum of empty slice is zero
// we only care about the previous state, so O(1) space is possible
impl Solution {
    pub fn max_sum_div_three(nums: Vec<i32>) -> i32 {
        nums.into_iter()
            // we use i32::MIN as -inf, which might cause problem
            // if any sum might exceed abs(i32::MIN)
            // but is fine for us
            .fold((0, i32::MIN, i32::MIN), |(z, o, t), v| match v % 3 {
                1 => (z.max(t + v), o.max(z + v), t.max(o + v)),
                2 => (z.max(o + v), o.max(t + v), t.max(z + v)),
                _ => (z + v, o + v, t + v),
            })
            .0
    }
}