leetcode 周赛 163 5265. 可被三整除的最大和 python 解法

目录

1. 解答

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/greatest-sum-divisible-by-three
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

这道题我 wa 了一次。

先看一个简洁的解法：

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

我的解法：

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        x = self.s(nums)
        nums.reverse()
        return max(x, self.s(nums))

    def s(self, nums: List[int]) -> int:
        dp = [[0,0,0] for i in range(len(nums))]
        dp[0][nums[0] % 3] = nums[0]
        for i in range(1, len(nums)):
            dp[i][0] = dp[i-1][0]
            dp[i][1] = dp[i-1][1]
            dp[i][2] = dp[i-1][2]
            for j in range(3):
                if dp[i-1][j] != 0:
                    dp[i][(j+nums[i])%3] = max(nums[i] + dp[i-1][j], dp[i][(j+nums[i])%3])
        return dp[-1][0]

我第一次提交只是 s(nums) 结果有的数据算出来不是最大值。