1262. 可被三整除的最大和

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

题目描述

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

前置知识

数组
回溯法
排序

暴力法

公司

字节
网易有道

思路

一种方式是找出所有的能够被 3 整除的子集，然后挑选出和最大的。由于我们选出了所有的子集，那么时间复杂度就是 $O(2^N)$ ，毫无疑问会超时。这里我们使用回溯法找子集，如果不清楚回溯法，可以参考我之前的题解，很多题目都用到了，比如78.subsets。

更多回溯题目，可以访问上方链接查看（可以使用一套模板搞定）：

代码

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        self.res = 0
        def backtrack(temp, start):
            total = sum(temp)
            if total % 3 == 0:
                self.res = max(self.res, total)
            for i in range(start, len(nums)):
                temp.append(nums[i])
                backtrack(temp, i + 1)
                temp.pop(-1)


        backtrack([], 0)

        return self.res

减法 + 排序

减法的核心思想是，我们求出总和。如果总和不满足题意，我们尝试减去最小的数，使之满足题意。

思路

这种算法的思想，具体来说就是：

我们将所有的数字加起来，我们不妨设为 total
total 除以 3，得到一个余数 mod， mod 可能值有 0，1，2.
同时我们建立两个数组，一个是余数为 1 的数组 one，一个是余数为 2 的数组 two
如果 mod 为 0，我们直接返回即可。
如果 mod 为 1，我们可以减去 one 数组中最小的一个（如果有的话），或者减去两个 two 数组中最小的（如果有的话），究竟减去谁取决谁更小。
如果 mod 为 2，我们可以减去 two 数组中最小的一个（如果有的话），或者减去两个 one 数组中最小的（如果有的话），究竟减去谁取决谁更小。

由于我们需要取 one 和 two 中最小的一个或者两个，因此对数组 one 和 two 进行排序是可行的，如果基于排序的话，时间复杂度大致为 $O(NlogN)$，这种算法可以通过。

以题目中的例 1 为例：

以题目中的例 2 为例：

代码

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        one = []
        two = []
        total = 0

        for num in nums:
            total += num
            if num % 3 == 1:
                one.append(num)
            if num % 3 == 2:
                two.append(num)
        one.sort()
        two.sort()
        if total % 3 == 0:
            return total
        elif total % 3 == 1 and one:
            if len(two) >= 2 and one[0] > two[0] + two[1]:
                return total - two[0] - two[1]
            return total - one[0]
        elif total % 3 == 2 and two:
            if len(one) >= 2 and two[0] > one[0] + one[1]:
                return total - one[0] - one[1]
            return total - two[0]
        return 0

减法 + 非排序

思路

上面的解法使用到了排序。我们其实观察发现，我们只是用到了 one 和 two 的最小的两个数。因此我们完全可以在线形的时间和常数的空间完成这个算法。我们只需要分别记录 one 和 two 的最小值和次小值即可，在这里，我使用了两个长度为 2 的数组来表示，第一项是最小值，第二项是次小值。

代码

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        one = [float('inf')] * 2
        two = [float('inf')] * 2
        total = 0

        for num in nums:
            total += num
            if num % 3 == 1:
                if num < one[0]:
                    t = one[0]
                    one[0] = num
                    one[1] = t
                elif num < one[1]:
                    one[1] = num
            if num % 3 == 2:
                if num < two[0]:
                    t = two[0]
                    two[0] = num
                    two[1] = t
                elif num < two[1]:
                    two[1] = num
        if total % 3 == 0:
            return total
        elif total % 3 == 1 and one:
            if len(two) >= 2 and one[0] > two[0] + two[1]:
                return total - two[0] - two[1]
            return total - one[0]
        elif total % 3 == 2 and two:
            if len(one) >= 2 and two[0] > one[0] + one[1]:
                return total - one[0] - one[1]
            return total - two[0]
        return 0

有限状态机

思路

我在数据结构与算法在前端领域的应用 - 第二篇中讲到了有限状态机。

状态机表示若干个状态以及在这些状态之间的转移和动作等行为的数学模型。通俗的描述状态机就是定义了一套状态変更的流程：状态机包含一个状态集合，定义当状态机处于某一个状态的时候它所能接收的事件以及可执行的行为，执行完成后，状态机所处的状态。

状态机使用非常广泛，比如正则表达式的引擎，编译器的词法和语法分析，网络协议，企业应用等很多领域都会用到。

拿本题中来说，我们从左到右扫描数组的过程，将会不断改变状态机的状态。

我们使用 state 数组来表示本题的状态：

state[0] 表示 mod 为 0 的最大和
state[1] 表示 mod 为 1 的最大和
state[2] 表示 mod 为 1 的最大和

我们的状态转移方程就会很容易。说到状态转移方程，你可能会想到动态规划。没错！这种思路可以直接翻译成动态规划，算法完全一样。如果你看过我上面提到的文章，那么状态转移方程对你来说就会很容易。如果你不清楚，那么请往下看：

我们从左往右不断读取数字，我们不妨设这个数字为 num。
如果 num % 3 为 0。那么我们的 state[0], state[1], state[2] 可以直接加上 num（题目限定了 num 为非负），因为任何数字加上 3 的倍数之后，mod 3 的值是不变的。
如果 num % 3 为 1。我们知道 state[2] + num 会变成一个能被三整除的数，但是这个数字不一定比当前的 state[0]大。代码表示就是max(state[2] + num, state[0])。同理 state[1] 和 state[2] 的转移逻辑类似。
同理 num % 3 为 2 也是类似的逻辑。
最后我们返回 state[0]即可。

代码

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        state = [0, float('-inf'), float('-inf')]

        for num in nums:
            if num % 3 == 0:
                state = [state[0] + num, state[1] + num, state[2] + num]
            if num % 3 == 1:
                a = max(state[2] + num, state[0])
                b = max(state[0] + num, state[1])
                c = max(state[1] + num, state[2])
                state = [a, b, c]
            if num % 3 == 2:
                a = max(state[1] + num, state[0])
                b = max(state[2] + num, state[1])
                c = max(state[0] + num, state[2])
                state = [a, b, c]
        return state[0]

当然这个代码还可以简化：

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        state = [0, float('-inf'), float('-inf')]

        for num in nums:
            temp = [0] * 3
            for i in range(3):
                temp[(i + num) % 3] = max(state[(i + num) % 3], state[i] + num)
            state = temp

        return state[0]