Leetcode 1262：可被三整除的最大和（超详细的解法！！！）

2024-07-17 12:13| 来源: 网络整理| 查看: 265

给你一个整数数组 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 int: n = len(nums) dp = [[0]*3 for _ in range(n + 1)] for i in range(1, n + 1): for j in range(3): a = dp[i - 1][(j + 3 - nums[i-1]%3) % 3] + nums[i-1] if a % 3 == j: dp[i][j] = max(dp[i-1][j], a) else: dp[i][j] = dp[i-1][j] return dp[-1][0]

还可以更加简洁。定义 f ( i ) f(i) f(i)表示当前满足sum%3==i的最大sum是多少，那么

f ( ( f ( i ) + a ) % 3 ) = m a x ( f ( ( f ( i ) + a ) % 3 ) , f ( i ) + a ) f((f(i) + a)\%3)=max(f((f(i)+a)\%3), f(i) + a) f((f(i)+a)%3)=max(f((f(i)+a)%3),f(i)+a)

其中a表示nums中的每个数。

class Solution: def maxSumDivThree(self, nums: List[int]) -> int: dp = [0, 0, 0] for a in nums: for i in dp[:]: dp[(i + a) % 3] = max(dp[(i + a) % 3], i + a) return dp[0]

reference:

https://leetcode.com/problems/greatest-sum-divisible-by-three/discuss/431077/Python-One-Pass-O(1)-space

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题，希望大家指出！！！

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章