1262. Greatest Sum Divisible by Three

Link

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

Solution

    public int maxSumDivThree(int[] A) {
        //dp[0] : the max sum which %3==0, shall be init by 0, no select so far
        //dp[1] : the max sum which %3==1, not existed, Integer.MIN_VALUE
        //dp[2] : the max sum which %3==2, not existed, Integer.MIN_VALUE
        
        int[] dp = {0, Integer.MIN_VALUE, Integer.MIN_VALUE};
        
        for(int num : A){
            //for each num in A, consider it's impact on the dp, 
            // and save new resulting dp to temp
            int[] temp = new int[3];
            for(int i = 0; i < 3; i++){
                //not take num, temp[(i+num)%3] = dp[(i+num)%3], reuse previoud      
                //take it 
                temp[(i+num)%3] = Math.max(dp[(i+num)%3], num + dp[i]);
            }
            dp = temp;
        }
        return dp[0];
    }