力扣---1262. 可被三整除的最大和

给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。

示例 1：
输入：nums = [3,6,5,1,8]
输出：18
解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。

示例 2：
输入：nums = [4]
输出：0
解释：4 不能被 3 整除，所以无法选出数字，返回 0。

示例 3：
输入：nums = [1,2,3,4,4]
输出：12
解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。

提示：
    1 <= nums.length <= 4 * 10^4
    1 <= nums[i] <= 10^4
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/greatest-sum-divisible-by-three
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题可以用两种方法来做，一种是动态规划，一种是纯粹的数学方法。

讲解放注释了，其他没啥需要注意的地方。

代码如下：

数学方法：

class Solution {
    public int maxSumDivThree(int[] nums) {
        int res = 0;
        //存储余1的数
        List<Integer> list1 = new ArrayList<>();
        //存储余2的数
        List<Integer> list2 = new ArrayList<>();
        for (int i : nums) {
            if (i % 3 == 1) {
                list1.add(i);
            } else if (i % 3 == 2) {
                list2.add(i);
            }
            res += i;
        }
        //可以整除代表所有的数字之和符合题意，直接返回
        if (res % 3 == 0) {
            return res;
        }
        //从小到大排序
        list1.sort((a, b) -> (a - b));
        list2.sort((a, b) -> (a - b));
        if (res % 3 == 1) {
            //考虑列表越界情况。
            if (list1.size() > 0) {
                if (list2.size() > 1) {
                    //余数为1时，答案等于所有数字之和减去一个余数为1的数字，或者减去两个余数为2的数字。
                    res -= Math.min(list1.get(0), list2.get(0) + list2.get(1));
                } else {
                    res -= list1.get(0);
                }
            } else {
                res -= list2.get(0) + list2.get(1);
            }
        } else {
            //考虑列表越界情况。
            if (list1.size() > 1) {
                if (list2.size() > 0) {
                    //余数为2时，答案等于所有数字之和减去两个余数为1的数字，或者减去一个余数为2的数字。
                    res -= Math.min(list2.get(0), list1.get(0) + list1.get(1));
                } else {
                    res -= list1.get(0) + list1.get(1);
                }
            } else {
                res -= list2.get(0);
            }
        }
        return res;
    }
}

运行结果：

动态规划

class Solution {
    public int maxSumDivThree(int[] nums) {
        //由于余数为0，1,2的和在之后都有可能变成余数为0，所以需要同时维护三种情况的最大值。
        int[] dp = new int[3];
        for (int num : nums) {
            // 三种情况都加，判断最大值。
            int a = dp[0] + num;
            int b = dp[1] + num;
            int c = dp[2] + num;
            dp[a % 3] = Math.max(dp[a % 3], a);
            dp[b % 3] = Math.max(dp[b % 3], b);
            dp[c % 3] = Math.max(dp[c % 3], c);
        }
        return dp[0];
    }
}

运行结果：