[LeetCode] 1262. Greatest Sum Divisible by Three

[grandyang]

Given an array nums of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.

Example 1:

Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

Example 2:

Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.

Example 3:

Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).

Constraints:

• 1 <= nums.length <= 4 * 10^4
• 1 <= nums[i] <= 10^4

这道题给了一个数组 nums，让找出最大的元素之和，使得其可以整除3，注意这里不是子数组之和，并不需要连续，而是相当于某个子集之和。所以博主最先想到的方法是用类似 Subsets 中的方法生成所有的子集，并在生成的过程中计算每个子集的数字之和，然后判断若能整除3，则更新结果 res，但是这种方法却超时了。博主心想就一道 Medium 的题难道还需要用什么高端的方法，原来真的是有很高效的解法呢！首先来分析这道题，数字之和需要除以3，那么余数只有三种情况，余数为0即为整除，也是本题需要求解的情况，或者是余数为1或者为2。最好的情况就是整个数组之和除以3正好余数为0，这也是最大的数字之和，但是当整个数组之和除以3余1怎么办？如果能在数组中找到一个除以3余1的数字，那么整个数组之和减去这个数字后一定能被3整除，这应该是小学学过的某种定理吧，即若a除以c的余数和b除以c的余数相同，则 a-b 一定可以整除c。

回到本题，为了使剩余的数字之和最大，减去的那个除以3余1的数字应该越小越小，同理，若整个数组之和除以3余2，则减去一个最小的除3余2的数字。于是这道题就变成了分别寻找最小的除3余2，除3余1的数（也可以是若个数之和），用 leftOne 和 leftTwo 来表示，既然要找最小值，则初始化应该是最大数，但这里这不能直接初始化为整型最大值，因为后面还会做加法运算可能导致整型溢出。由于题目限定了数字的大小不超过 10^4，就用这个当初始值就可以了。然后遍历整个数组，先将遍历到的数字 num 加到结果 res 中，然后就要更新 leftOne 和 leftTwo 了，判断若 num 除以3余1的话，则可以用 leftOne+num 来更新 leftTwo，因为两个除3余1的数相加就会除3余2，然后再用 num 来更新 leftOne。同理，若 num 除以3余2的话，则可以用 leftTwo+num 来更新 leftOne，因为两个除3余2的数相加就会除3余1，然后再用 num 来更新 leftTwo。这样最后只要看数组之和 res 是否能整除3，能的话直接返回 res，若余1的话，返回 res-leftOne，否则返回 res-leftTwo 即可，参见代码如下：

解法一：

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int res = 0, leftOne = 1e4, leftTwo = 1e4;
        for (int num : nums) {
            res += num;
            if (num % 3 == 1) {
                leftTwo = min(leftTwo, leftOne + num);
                leftOne = min(leftOne, num);
            } else if (num % 3 == 2) {
                leftOne = min(leftOne, leftTwo + num);
                leftTwo = min(leftTwo, num);
            }
        }
        if (res % 3 == 0) return res;
        if (res % 3 == 1) return res - leftOne;
        return res - leftTwo;
    }
};

上面的解法是比较巧妙，但估计比较难想，这道题给的 hint 是要用动态规划 Dynamic Programming 来做，这里我们定义的 dp 数组和题目中提示不太一样，这里定义一个 n+1 by 3 的二维数组，其中 dp[i][j] 表示前i个数字中的最大的数字之和且其除以3余 3-j，为什么要这么定义呢？这跟后面的状态转移方程有关，由于j只有三个状态 0，1，和2，所以可以分别来更新。

对于 dp[i][0] 来说，至少可以用 dp[i-1][0] 来更新，即不选择当前这个数字 num。若选择当前的数字 num，其不一定会被3整除，但是 dp[i-1][num%3] + num 一定会被3整除，这是为啥呢？首先，若 num 能被3整除，则这个表达肯定也能被3整除，没有问题。若 num 除3余1，这样的话就是 dp[i-1][1] + num 了，根据上面说的 dp 的定义，dp[i-1][1] 表示前 i-1 个数字中的最大数字之和且其除3余2，而 num 正好是一个除3余1的数，加上之后就可以被3整除了，所以可以用来更新 dp[i][0]。同理，若 num 除3余2，就是用 dp[i-1][2] + num 跟 dp[i-1][0] 相比，取较大值更新 dp[i][0]。

对于 dp[i][1] 来说，至少可以用 dp[i-1][1] 来更新，即不选择当前这个数字 num。若选择当前的数字 num，其不一定会是除3余2的，但是 dp[i-1][(num+1)%3] + num 一定会是除3余2的，这是为啥呢？首先，若 num 能被3整除，则 num+1 是除3余1的，代入得到 dp[i-1][1] 是除3余2的，加上 num 还是除3余2的。对于 num 除3余1的情况，代入可以得到 dp[i-1][2] + num，根据上面说的 dp 的定义，dp[i-1][2] 表示前 i-1 个数字中的最大数字之和且除以3余1，而 num 正好也是一个除3余1的数，加上之后整个就是除3余2的了，所以可以用来更新 dp[i][1]。同理，若 num 除3余2，就是用 dp[i-1][1] + num 跟 dp[i-1][2] 相比，取较大值更新 dp[i][2]。

对于 dp[i][2] 的更新这里就不讲了，跟上面的情况大同小异，最终的结果保存在 dp[n][0] 中，若觉得上面的讲解很绕，不容易理解的话，这里建议使用题目中的例子1来一步一步推，观察 dp 数组的每个数字的更新，这样就可以理解了，参见代码如下：

解法二：

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n + 1, vector<int>(3));
        dp[0] = {0, INT_MIN, INT_MIN};
        for (int i = 1; i <= n; ++i) {
            int idx = i - 1;
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][nums[idx] % 3] + nums[idx]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][(nums[idx] + 1) % 3] + nums[idx]);
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][(nums[idx] + 2) % 3] + nums[idx]);
        }
        return dp[n][0];
    }
};

再来看一种一维 dp 数组的解法，这个可不是上面的 dp 解法的省空间版本啊，二者的余数定义不同。这里的 dp[i] 表示整个数组的最大和且除3余i。下面来分析状态转移方程，遍历数组的每一个数组 num，由于 dp 是一维数组，没有多余的维度去保存上一轮的状态值，所以之前的状态值也都保存在 dp 中，为了不混淆上一轮和当前轮的 dp 值，在更新 dp 之前，把当前已有的 dp 值保存到一个临时数组 t 中，遍历t数组，当前遍历到的数字i除以3余几并不重要，其加上新数字 num 之后再对3取余，就是要更新的 dp 位置，用 i+num 去更新即可，参见代码如下：

解法三：

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

Github 同步地址:

#1262

参考资料：

https://leetcode.com/problems/greatest-sum-divisible-by-three/

https://leetcode.com/problems/greatest-sum-divisible-by-three/discuss/431077/JavaC%2B%2BPython-One-Pass-O(1)-space

https://leetcode.com/problems/greatest-sum-divisible-by-three/discuss/431108/Java-O(N)-solution-Simple-Math-O(1)-space

https://leetcode.com/problems/greatest-sum-divisible-by-three/discuss/431785/C%2B%2B-Commented-DP-solution-that-actually-makes-sense.

LeetCode All in One 题目讲解汇总(持续更新中...)

喜欢请点赞，疼爱请打赏❤️~.~

微信打赏

|

Venmo 打赏

---|---