可被三整除的最大和 图解题解

可被三整除的最大和，到底在挑什么样的子集

给一个整数数组 nums，挑若干个数（可以一个不挑），要挑出的和能被 3 整除且最大。空集也合法（和 0），答案最差 0、永不为负。以 [3,6,5,1,8] 为例，答案 18，挑出 3、6、1、8。

n 个数每个挑或不挑，2ⁿ 种子集为什么试不完

n 个数各挑或不挑，全摆出来就是 2ⁿ 种子集，n 到 4 万逐个验根本跑不完。有用的信息只有一个：这堆数的和除以 3 的余数（取模，除以 3 只可能余 0、1、2）。和本身可以很大，但余数相同的两堆，对后面能不能凑成被 3 整除的影响完全一样。

只记余数不记具体的和，三个桶怎么就够了

既然只有余数要紧，就用动态规划（把『和除以 3 余 j 时的最大和』算一次存下、后面直接取）记账。定义 f[j] 为「和除以 3 余 j 时的最大和」，f[j] 就叫状态（某局面下的最优结果）。余数只有 0、1、2，故永远三个桶 f[0]、f[1]、f[2]。起手没挑数，和 0、余 0，f[0]=0；余 1、余 2 此刻凑不出来，填极小哨兵（比任何真实和都小的「不可能」标记）。

来一个新数，三个桶各自该接上一行的哪一列

每来一个新数 x，先看它除以 3 余几，记作 r。要让新余数落在 j，前面那部分就得余 (j-r) 调正到 0~2 的那个数，因为 (j-r)+r 除以 3 正好余 j。于是每个桶 f[j] 有两条来路：不挑 x 保留旧的 f[j]；或把 x 接到旧的 f[(j-r)] 桶上加个 x，两者取较大者，这一步叫状态转移（由旧状态推出新状态的规则）。注意接的常不是同名桶：余 2 的数想凑余 0，接的是旧的余 1 桶。全部处理完答案在 f[0]，即总和整除时的最大和。

拿 [3,6,5,1,8] 把三个桶从头滚一遍

起手三桶 [0, 极小, 极小]（对应余 0、1、2）。数 3（余 0）接旧余 0：0+3=3。数 6（余 0）：3+6=9。数 5（余 2）凑余 2 接旧余 0：9+5=14。数 1（余 1）：凑余 0 接旧余 2 得 max(9, 14+1)=15，凑余 1 接旧余 0 得 10，得 [15, 10, 14]。数 8（余 2）：凑余 0 接旧余 1 得 max(15, 10+8)=18，凑余 1 得 22，凑余 2 得 23，得 [18, 22, 23]。答案取 f[0]=18，即题面所求；相当于从总和 23（余 2）舍掉余 2 的 5，剩 3、6、1、8 恰好 18。

哨兵图省事写成 0，答案为什么会凭空冒出个不合法的和

余 1、余 2 桶的初值一旦图省事写成 0，后面就会接出根本不存在的方案，它俩必须是极小哨兵。Java、C++ 里 (j-x) 取模会得到负数、当下标就越界，得写成 ((j-x)%3+3)%3 掰回 0~2。还有答案取 f[0]，别看 f[2] 常更大就返回它——它的和余 2、不合法。

从头扫一遍数组，每个数固定更新 3 个桶，总时间与数组长度成正比，记作 O(n)（大 O 记号，规模变大时运算量的增长量级）。参考代码开 (n+1)×3 的表，空间 O(n)；每行只依赖上一行，用三个变量滚动覆盖能压到 O(1)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        n = len(nums)
        f = [[-inf] * 3 for _ in range(n + 1)]
        f[0][0] = 0
        for i, x in enumerate(nums, 1):
            for j in range(3):
                f[i][j] = max(f[i - 1][j], f[i - 1][(j - x) % 3] + x)
        return f[n][0]

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int n = nums.size();
        const int inf = 1 << 30;
        int f[n + 1][3];
        f[0][0] = 0;
        f[0][1] = f[0][2] = -inf;
        for (int i = 1; i <= n; ++i) {
            int x = nums[i - 1];
            for (int j = 0; j < 3; ++j) {
                f[i][j] = max(f[i - 1][j], f[i - 1][(j - x % 3 + 3) % 3] + x);
            }
        }
        return f[n][0];
    }
};

Java

import java.util.*;
class Solution {
    public int maxSumDivThree(int[] nums) {
        int n = nums.length;
        final int inf = 1 << 30;
        int[][] f = new int[n + 1][3];
        f[0][1] = f[0][2] = -inf;
        for (int i = 1; i <= n; ++i) {
            int x = nums[i - 1];
            for (int j = 0; j < 3; ++j) {
                f[i][j] = Math.max(f[i - 1][j], f[i - 1][(j - x % 3 + 3) % 3] + x);
            }
        }
        return f[n][0];
    }
}