What is the approach for solving the Greatest Sum Divisible by Three?

The solution uses dynamic programming with state transitions, represented as DP[pos][mod], to track the maximum possible sum divisible by three.

How can I optimize this problem using greedy algorithms?

Sorting the array based on modulo 3 values and selecting numbers greedily can optimize the solution, though dynamic programming is the most efficient method.

What is the time complexity of the solution?

The time complexity depends on the approach, usually O(n) or O(n * 3), where n is the length of the array.

Can this approach be extended to multidimensional arrays?

Yes, the state transition dynamic programming approach can be adapted for multidimensional arrays, increasing the problem's complexity.

What should I consider when implementing the solution?

Ensure that you correctly manage the modulo 3 states and handle edge cases where no sum is divisible by three.

#1262

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

可被三整除的最大和

给你一个整数数组 nums ，请你找出并返回能被三整除的元素最大和。示例 1：输入： nums = [3,6,5,1,8] 输出： 18 解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。示例 2：输入： nums = [4] 输出： 0 解释： 4 …

数组动态规划贪心排序

题目描述

给你一个整数数组 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⁴

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示前 $i$ 个数中选取若干个数，使得这若干个数的和模 $3$ 余 $j$ 的最大值。初始时 $f[0][0]=0$ ，其余为 $-\infty$ 。

对于 $f[i][j]$ ，我们可以考虑第 $i$ 个数 $x$ 的状态：

如果我们不选 $x$ ，那么 $f[i][j]=f[i-1][j]$ ；
如果我们选 $x$ ，那么 $f[i][j]=f[i-1][(j-x \bmod 3 + 3)\bmod 3]+x$ 。

因此我们可以得到状态转移方程：

f[i][j]=\max\{f[i-1][j],f[i-1][(j-x \bmod 3 + 3)\bmod 3]+x\}

最终答案为 $f[n][0]$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $nums$ 的长度。

注意到 $f[i][j]$ 的值只与 $f[i-1][j]$ 和 $f[i-1][(j-x \bmod 3 + 3)\bmod 3]$ 有关，因此我们可以使用滚动数组优化空间复杂度，使空间复杂度降低为 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        n = len(nums)
        f = [[-inf] * 3 for _ in range(n + 1)]
        f[0][0] = 0
        for i, x in enumerate(nums, 1):
            for j in range(3):
                f[i][j] = max(f[i - 1][j], f[i - 1][(j - x) % 3] + x)
        return f[n][0]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ability to recognize state transition patterns in dynamic programming.
question_mark
Understanding of greedy techniques for optimizing the sum.
question_mark
Comfort with handling arrays and ensuring the sum is divisible by three.

warning

常见陷阱

外企场景

error
Not properly managing the modulo 3 states during dynamic programming updates.
error
Confusing the maximum sum with the largest number divisible by three.
error
Incorrectly handling edge cases where no sum is divisible by three.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to find the minimum sum divisible by three.
arrow_right_alt
Extend the problem to include negative integers in the array.
arrow_right_alt
Apply this approach to a multidimensional array for greater complexity.

help

常见问题

外企场景

继续练习

#1363 形成三的最大倍数 #646 最长数对链 #435 无重叠区间