面试刷题：能被3整除的最大和
By 青衣极客 Blue Geek In 2020-04-01
“动态规划”在解决算法问题时常常涉及到，也是一种非常重要的问题求解思想。不过，其描述太过宽泛，以至于很多的算法实际上都可以归为“动态规划”。因此，单独来说动态规划是没有什么太大意义的，因为即使知晓其思想，在解决实际遇到的问题时仍然一头雾水。接下来我们要讨论的一道题目就可以使用“动态规划”来解决，但是在想明白其中的逻辑之前，常常让人陷入逻辑的混乱；而一旦想清楚逻辑，就变得非常简单。
1. 题目 Q1262 能被3整除的最大和
给定一个整数数组nums，我们需要从中找出可能的最大的能被3整除的和。
约束条件
(a) 1 <= nums.length <= 4 * 10^4
(b) 1 <= nums[i] <= 10^4
示例1
Input: nums = [3,6,5,1,8]
Output: 18
解释： 3+6+1+8=18
示例2
Input: nums = [4]
Output: 0
解释： 不存在求和能被3整除的数字
示例3
Input: nums = [1,2,3,4,4]
Output: 12
解释： 1+3+4+4=12
2. 解题思路
一个整数除以3有三种情况：(1) 整除，即余数为0；(2) 余数为1；(3) 余数为2。两个整数之和除以3的情况也是以上的这三种，因此在求和前后的所有状态构成了一个封闭的有限集合，即有限状态机。如果我们能够在每次求和之后都能及时记录这三种状态的情况，那么在所有整数都相加完成之后，最终余数为0的状态所记录的数字就是本问题的结果。
我们可以使用伪代码更加清晰地描述这个思路解决问题的过程：
Input: nums, n x int
Init: rem_0 = -MAX, rem_1 = -MAX, rem_2 = -MAX
-------------------------
For num in nums:
if num % 3 == 0:
rem_0 = max(rem_0 + num, num)
rem_1 = rem_1 + num if rem_1 > 0 else rem_1
rem_2 = rem_2 + num if rem_2 > 0 else rem_2
else if num % 3 == 1:
mid = rem_0
rem_0 = max(rem_0, rem_2 + num) if rem_2 > 0 else rem_0
rem_2 = max(rem_2, rem_1 + num) if rem_1 > 0 else rem_2
rem_1 = max(rem_1, max(mid+v, v))
else:
mid = rem_0
rem_0 = max(rem_0, rem_1 + num) if rem_1 > 0 else rem_0
rem_1 = max(rem_1, rem_2 + num) if rem_2 > 0 else rem_1
rem_2 = max(rem_2, max(mid + num, num))
-------------------------
Output: rem_0 if rem_0 > 0 else 0
以上伪代码描述了每加一个新的整数会将状态机中的三种状态记录改变成什么样子。对于余数为0的整数，不会导致状态机的各种状态之间的转换；对于余数为1的整数，会使得rem_0转换为rem_1, rem_1转换为rem_2, rem_2转换为rem_0;对于余数为2的整数，会使得rem_0转换为rem_2, rem_1转换为rem_0，rem_2转换为rem_1。除此之外，还需要注意一点，即状态是否由整数和构成。我们可以给每个状态初始化一个最大的负整数，在第一次进入该状态时设置为正数，这样就可以通过正负判断该状态记录是否为整数和。
3. C++解决方案
由于约束条件中给出了整数的数值范围，因此，各个状态的初始记录数值可以设置为一个足够大的负数，而不需要是最大的负数。三个状态正好可以用一个3元素的数组描述，而不必写三个变量那么麻烦。最后，C++支持“问号表达式”，正好可以用于实现算法中多处简单的条件判断。
class Solution {
public:
// 48ms, faster than 92.89%
int maxSumDivThree(vector<int>& nums) {
// record states for remaider = 0,1,2 situations
vector<int> remainds{int(-4e8), int(-4e8), int(-4e8)};
int mid = 0;
for (auto & v : nums) {
if (v % 3 == 0) {
remainds[0] = max(remainds[0] + v, v);
remainds[1] = remainds[1] > 0 ? remainds[1] + v : remainds[1];
remainds[2] = remainds[2] > 0 ? remainds[2] + v : remainds[2];
} else if (v % 3 == 1) {
mid = remainds[0];
remainds[0] = remainds[2] > 0 ? max(remainds[0], remainds[2] + v) : remainds[0];
remainds[2] = remainds[1] > 0 ? max(remainds[2], remainds[1] + v) : remainds[2];
remainds[1] = max(remainds[1], max(mid + v, v));
} else {
mid = remainds[0];
remainds[0] = remainds[1] > 0 ? max(remainds[0], remainds[1] + v) : remainds[0];
remainds[1] = remainds[2] > 0 ? max(remainds[1], remainds[2] + v) : remainds[1];
remainds[2] = max(remainds[2], max(mid + v, v));
}
}
return max(0, remainds[0]);
}
};
这个问题之所以可以这样简单地使用时间复杂度为O(n)的算法解决，其中一个很重要的原因是：状态及其有限，仅有三个。这样就可以使用枚举的办法来记录所有的状态以及状态之间的转换规则。类似的问题还有跳台阶问题，每次只允许跳一步或者两步，那么当前台阶就必定是从上一步或者上上步台阶转换而来。这种有限状态之间的转换可以很容易地写出递推表达式，不过每个问题中需要特殊处理的初值也是需要注意的点。
COMMENT
博客评论区功能由Github Issue提供，提交Issue时请以本文标题为话题。
"BG78-面试刷题：能被3整除的最大和 Q1262"