1262. Greatest Sum Divisible by Three 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int maxSumDivThree(int[] nums) {
        // 定义 dp[i][j] 为前 i 个数中选择部分数字求和对 3 取模后值为 j 时的和
        int[][] dp = new int[nums.length + 1][3];
        dp[0][0] = 0; // 没有数字时和为 0
        dp[0][1] = Integer.MIN_VALUE; // 没有数字时和无法组成 1
        dp[0][2] = Integer.MIN_VALUE; // 没有数字时和无法组成 2

        for (int i = 1; i < dp.length; i++) {
            int mod = nums[i - 1] % 3;
            if (mod == 0) {
                dp[i][0] = dp[i - 1][0] + nums[i - 1];
                dp[i][1] = dp[i - 1][1] + nums[i - 1];
                dp[i][2] = dp[i - 1][2] + nums[i - 1];
            } else if (mod == 1) {
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] + nums[i - 1]);
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + nums[i - 1]);
                dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + nums[i - 1]);
            } else {
                // mod == 2
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + nums[i - 1]);
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2] + nums[i - 1]);
                dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][0] + nums[i - 1]);
            }
        }

        return dp[nums.length][0];
    }
}

References

1262. Greatest Sum Divisible by Three