可被三整除的最大和

给你一个整数数组 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 整除的最大和）

DFS（超时）

private int maxSum = 0;

public int maxSumDivThree (int[] nums) {
    dfs(nums, 0, 0);
    return maxSum;
}

public void dfs(int[] nums, int i, int sum) {
    if (i == nums.length) {
        if (sum % 3 == 0) {
            maxSum = Math.max(maxSum, sum);
        }
    } else {
        dfs(nums, i + 1, sum);
        dfs(nums, i + 1, sum + nums[i]);
    }
}

动态规划
dp[i]表示num%3=i时考虑到num时的最大和

状态转移方程:
nums[i] %3 = 0:
dp[0]=max(dp[0],dp[0]+nms[i]);
dp[1]=max(dp[1],dp[1]+nms[i]);
dp[2]=max(dp[2],dp[2]+nms[i]);

nums[i] %3 = 1:
dp[0]=max(dp[0],dp[2]+nms[i]);
dp[1]=max(dp[1],dp[0]+nms[i]);
dp[2]=max(dp[2],dp[1]+nms[i]);

nums[i] %3 = 2:
dp[0]=max(dp[0],dp[1]+nms[i]);
dp[1]=max(dp[0],dp[2]+nms[i]);
dp[2]=max(dp[0],dp[0]+nms[i]);

public int maxSumDivThree (int[] nums) {
    int[] dp = {0, Integer.MIN_VALUE, Integer.MIN_VALUE};
    for (int i = 0; i < nums.length; i++) {
        int mod = nums[i] % 3;
        int[] temp = new int[3];
        for (int j = 0; j < dp.length; j++) {
            temp[j] = Math.max(dp[j], dp[(3 - mod + j) % 3] + nums[i]);
        }
        dp = temp;
    }
    return dp[0];
}

贪心
在遍历过程中保留最小的2个余1值和最小的2个余2值

public int maxSumDivThree(int[] nums) {
    int sum = 0;
    int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE; // 余1
    int min3 = Integer.MAX_VALUE, min4 = Integer.MAX_VALUE; // 余2
    for (int num : nums) {
        sum += num;
        if (num % 3 == 1) {
            if (num < min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }
        } else if (num % 3 == 2) {
            if (num < min3) {
                min4 = min3;
                min3 = num;
            } else if (num < min4) {
                min4 = num;
            }
        }
    }
    if (sum % 3 == 0) {
        return sum;
    }
    if (sum % 3 == 1) {
        if (min3 == Integer.MAX_VALUE || min4 == Integer.MAX_VALUE) {
            return sum - min1;
        }
        return sum - Math.min(min1, min3 + min4);
    }
    if (min1 == Integer.MAX_VALUE || min2 == Integer.MAX_VALUE) {
        return sum - min3;
    }
    return sum - Math.min(min3, min1 + min2);
}