[LeetCode] 1262. Greatest Sum Divisible by Three
grandyang opened this issue · 0 comments
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^41 <= 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 同步地址:
参考资料：
https://leetcode.com/problems/greatest-sum-divisible-by-three/
LeetCode All in One 题目讲解汇总(持续更新中...)
喜欢请点赞，疼爱请打赏❤️~.~
微信打赏
Venmo 打赏
---|---
