文章作者：Tyan 博客：noahsnail.com | CSDN | 简书
1. Description
2. Solution
**解析：**Version 1，是对Version 3的简化，具体参考Version 3。Version 2，先对数组求总和，然后根据每个数除3的余数进行有序分组，当总和除3余1时，此时总和应该减去最小的余数为1的数，或者减去最小的两个余数为2的数，如果二者同时有，则取二者的最小值，余数为2时同理。Version 3，dp用来维护最大和除3余数分别为0,1,2的状态，初始时，当余数为0时，不影响dp[0]的值，不需要更新dp[1],dp[2]，当余数为1,2时，此时才需要开始更新dp[1],dp[2]，然后根据余数的值不同，对各状态进行更新，pre用来保存上一轮结束时的状态。
- Version 1
class Solution:
def maxSumDivThree(self, nums: List[int]) -> int:
n = len(nums)
stat = [0, 0, 0]
for i in range(n):
for x in stat[:]:
remainder = (x nums[i]) % 3
stat[remainder] = max(stat[remainder], x nums[i])
return stat[0]- Version 2
class Solution:
def maxSumDivThree(self, nums: List[int]) -> int:
total = sum(nums)
n = len(nums)
one = []
two = []
for i in range(n):
if nums[i] % 3 == 1:
bisect.insort(one, nums[i])
elif nums[i] % 3 == 2:
bisect.insort(two, nums[i])
if total % 3 == 1:
if len(one) == 0:
total -= (two[0] two[1])
elif len(two) < 2:
total -= one[0]
else:
total -= min(one[0], two[0] two[1])
elif total % 3 == 2:
if len(two) == 0:
total -= (one[0] one[1])
elif len(one) < 2:
total -= two[0]
else:
total -= min(one[0] one[1], two[0])
return total- Version 3
class Solution:
def maxSumDivThree(self, nums: List[int]) -> int:
dp = [0, -float('inf'), -float('inf')]
for num in nums:
pre = dp[:]
if num % 3 == 0:
dp[0] = max(pre[0] num, pre[0])
dp[1] = max(pre[1] num, pre[1])
dp[2] = max(pre[2] num, pre[2])
elif num % 3 == 1:
dp[0] = max(pre[2] num, pre[0])
dp[1] = max(pre[0] num, pre[1])
dp[2] = max(pre[1] num, pre[2])
else:
dp[0] = max(pre[1] num, pre[0])
dp[1] = max(pre[2] num, pre[1])
dp[2] = max(pre[0] num, pre[2])
return dp[0]Reference
- https://leetcode.com/problems/greatest-sum-divisible-by-three/
