【1262. 可被三整除的最大和】-Toy模板网

这篇具有很好参考价值的文章主要介绍了【1262. 可被三整除的最大和】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

来源：力扣（LeetCode）

描述：

给你一个整数数组 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⁴
1 <= nums[i] <= 10⁴

方法：贪心 + 正向思维

我们把数组中的数分成三部分 a, b, c，它们分别包含所有被 3 除余 0 , 1, 2 的数。显然，我们可以选取 a 中所有的数，而对于 b 和 c 中的数，我们需要根据不同的情况选取不同数量的数。

假设我们在 b 中选取了 cnt_b 个数，c 中选取了 cnt_c个数，那么这些数的和被 3 除的余数为：

(cnt _b + 2 × cnt _c)mod3 = (cnt _b − cnt _c)mod3

我们希望上式的值为 0，那么 cnt_b 和 cnt_c 模 3 同余。并且我们可以发现，cnt_b 一定至少为 ∣b∣ − 2，其中 ∣b∣ 是数组 b 中的元素个数。这是因为如果 cnt_b ≤ ∣b∣ − 3，我们可以继续在 b 中选择 3 个数，使得 cnt_b 和 cnt_c 仍然模 3 同余。同理，cnt_c 一定至少为 ∣c∣ − 2。

因此，cnt_b 的选择范围一定在 {∣b∣−2, ∣b∣−1, ∣b∣} 中，cnt_c 的选择范围一定在 {∣c∣−2, ∣c∣−1, ∣c∣} 中。我们只需要使用两重循环，枚举最多 3 × 3 = 9 种情况。在从 b 或 c 中选取数时，我们可以贪心地从大到小选取数，因此需要对 b 和 c 进行排序。

代码：

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        // 使用 v[0], v[1], v[2] 分别表示 a, b, c
        vector<int> v[3];
        for (int num: nums) {
            v[num % 3].push_back(num);
        }
        sort(v[1].begin(), v[1].end(), greater<int>());
        sort(v[2].begin(), v[2].end(), greater<int>());

        int ans = 0;
        int lb = v[1].size(), lc = v[2].size();
        for (int cntb = lb - 2; cntb <= lb; ++cntb) {
            if (cntb >= 0) {
                for (int cntc = lc - 2; cntc <= lc; ++cntc) {
                    if (cntc >= 0 && (cntb - cntc) % 3 == 0) {
                        ans = max(ans, accumulate(v[1].begin(), v[1].begin() + cntb, 0) + accumulate(v[2].begin(), v[2].begin() + cntc, 0));
                    }
                }
            }
        }
        return ans + accumulate(v[0].begin(), v[0].end(), 0);
    }
};

执行用时：28 ms, 在所有 C++ 提交中击败了88.94%的用户
内存消耗：26.7 MB, 在所有 C++ 提交中击败了31.80%的用户
复杂度分析
时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。对 b 和 c 进行排序需要 O(nlogn) 的时间。两重循环枚举的 9 种情况可以看作常数，每一种情况需要 O(n) 的时间进行求和。
空间复杂度：O(n)，即为 a, b, c 需要使用的空间。

方法二：贪心 + 逆向思维

在方法一中，我们使用的是「正向思维」，即枚举 b 和 c 中分别选出了多少个数。我们同样也可以使用「逆向思维」，枚举 b 和 c 中分别丢弃了多少个数。

设 tot 是数组 nums 中所有元素的和，此时 tot 会有三种情况：

如果 tot 是 3 的倍数，那么我们不需要丢弃任何数；
如果 tot 模 3 余 1，此时我们有两种选择：要么丢弃 b 中最小的 1 个数，要么丢弃 c 中最小的 2 个数；
如果 tot 模 3 余 2，此时我们有两种选择：要么丢弃 b 中最小的 2 个数，要么丢弃 c 中最小的 1 个数。

我们同样可以对 b 和 c 进行排序，根据 tot 的情况来选出 b 或 c 中最小的 1 或 2 个数。

下面的代码中使用的是排序的方法。

代码：

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        // 使用 v[0], v[1], v[2] 分别表示 a, b, c
        vector<int> v[3];
        for (int num: nums) {
            v[num % 3].push_back(num);
        }
        sort(v[1].begin(), v[1].end(), greater<int>());
        sort(v[2].begin(), v[2].end(), greater<int>());
        int tot = accumulate(nums.begin(), nums.end(), 0);
        int remove = INT_MAX;

        if (tot % 3 == 0) {
            remove = 0;
        }
        else if (tot % 3 == 1) {
            if (v[1].size() >= 1) {
                remove = min(remove, v[1].end()[-1]);
            }
            if (v[2].size() >= 2) {
                remove = min(remove, v[2].end()[-2] + v[2].end()[-1]);
            }
        }
        else {
            if (v[1].size() >= 2) {
                remove = min(remove, v[1].end()[-2] + v[1].end()[-1]);
            }
            if (v[2].size() >= 1) {
                remove = min(remove, v[2].end()[-1]);
            }
        }

        return tot - remove;
    }
};

执行用时：32 ms, 在所有 C++ 提交中击败了76.27%的用户
内存消耗：26.7 MB,在所有 C++ 提交中击败了32.03%的用户
复杂度分析
时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。对 b 和 c 进行排序需要 O(nlogn) 的时间。也可以不用排序，将时间复杂度优化至 O(n)。
空间复杂度：O(n)，即为 a, b, c 需要使用的空间。如果不排序，可以不显示将 a, b, c 求出来，而是直接对数组 nums 进行一次遍历，找出模 3 余 1 和 2 的最小的两个数，将空间复杂度优化至 O(1)。

方法三：动态规划

在上面的两种方法中，我们都是基于贪心的思路，要么选择若干个较大的数，要么丢弃若干个较小的数。我们也可以使用动态规划的方法，不需要进行排序或者贪心，直接借助状态转移方程得出解。

记 f(i, j) 表示前 i (i ≥ 1) 个数中选取了若干个数，并且它们的和模 3 余 j (0 ≤ j < 3) 时，这些数的和的最大值。那么对于当前的数 nums[i]，如果我们选取它，那么就可以通过 f(i − 1, (j − nums[i]) mod 3) 转移得来；如果我们不选取它，就可以通过 f(i − 1, j) 转移得来。因此我们可以写出如下的状态转移方程：

f(i, j) = max{ f(i − 1, j), f(i − 1, (j − nums[i]) mod 3) + nums[i] }

边界条件为 f(0, 0) = 0 以及 f(0, 1) = f(0, 2) = −∞。表示当我们没有选取任何数时，和为 0，并且模 3 的余数为 0。对于 f(0, 1) 和 f(0, 2) 这两种不合法的状态，由于我们在状态转移中维护的是最大值，因此可以把它们设定成一个极小值。

在某些语言中，(j − nums[i]) mod 3 可能会引入负数，因此这道题用递推的形式来实现动态规划较为方便，即：

$\begin{cases} f(i−1, j) → f(i, j)\\ f(i−1,j)+nums[i]→f(i,(j+nums[i])mod3) \end{cases}$

我们还可以发现，所有的 f(i, ⋯) 只会从 f(i − 1, ⋯) 转移得来，因此在动态规划时只需要存储当前第 i 行以及上一行第 i − 1 行的结果，减少空间复杂度。

代码：

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        vector<int> f = {0, INT_MIN, INT_MIN};
        for (int num: nums) {
            vector<int> g = f;
            for (int i = 0; i < 3; ++i) {
                g[(i + num % 3) % 3] = max(g[(i + num % 3) % 3], f[i] + num);
            }
            f = move(g);
        }
        return f[0];
    }
};

执行用时：76 ms, 在所有 C++ 提交中击败了15.21%的用户
内存消耗：32.3 MB, 在所有 C++ 提交中击败了28.34%的用户
复杂度分析
时间复杂度：O(n)，其中 n 是数组 nums 的长度。
空间复杂度：O(1)。
author：LeetCode-Solution文章来源地址https://www.toymoban.com/news/detail-495648.html

到了这里，关于【1262. 可被三整除的最大和】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！