LeetCode1262.可被三整除的最大和

先贴上我写的笨笨的代码，但是超时了。。。我用DP把nums列表中所有元素可能出现的组合都枚举出来，判断是否被三整除；

class Solution(object):
    def maxSumDivThree(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ss = sum(nums)
        maxSumDivThree = 0
        # dp[i][j]数组表示:前i个元素可以组合成j为True,否则为False
        dp = [False] * (ss+1)
        dp[0] = True
        for i in range(len(nums)):
            for j in range(ss, nums[i]-1, -1):
                dp[j] = dp[j-nums[i]] or dp[j]
                if dp[j] and j%3==0 and j>maxSumDivThree:
                    maxSumDivThree = j
        return maxSumDivThree

该算法的复杂度为O(N*sum)，结果肯定就是：

于是，我学习了力扣大神的思路：动态规划与状态转移

定义

dp[i][0]表示nums[0...i]模三余零的最大和——零状态：当前数字最大和模三余零

dp[i][1]表示nums[0...i]模三余一的最大和——一状态：当前数字最大和模三余一

dp[i][2]表示nums[0...i]模三余二的最大和——二状态：当前数字最大和模三余二

 

 

 

 

def DPandState(self, nums):
    dp = [[0] * 3 for _ in range(len(nums)+1)]
    dp[0][1] = -1
    dp[0][2] = -1
    for i in range(1, len(nums)+1):
        if nums[i-1]%3 == 0:
            dp[i][0] = max(dp[i-1][0], dp[i-1][0]+nums[i-1])
            dp[i][1] = max(dp[i-1][1], dp[i-1][1]+nums[i-1])
            dp[i][2] = max(dp[i-1][2], dp[i-1][2]+nums[i-1])
        elif nums[i-1]%3 == 1:
            dp[i][0] = max(dp[i-1][0], dp[i-1][2]+nums[i-1])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]+nums[i-1])
            dp[i][2] = max(dp[i-1][2], dp[i-1][1]+nums[i-1])
        elif nums[i-1]%3 == 2:
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+nums[i-1])
            dp[i][1] = max(dp[i-1][1], dp[i-1][2]+nums[i-1])
            dp[i][2] = max(dp[i-1][2], dp[i-1][0]+nums[i-1])
    return dp[len(nums)][0]