leetcode 1262. 可被三整除的最大和

i 为行
j为列
t2=(dp[hang-1-i][0]+nums[hang-2-i])%3
dp[i-1][t2]=max(dp[hang-1-i][0]+nums[i-1],dp[i][t2],dp[i-1][t2])

class Solution(object):
    def maxSumDivThree(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #初始化数组
        hang=len(nums)
        lie=3
        dp=[[0]*lie for _ in range(hang)]

        i=len(nums)-1
        j=nums[i]%3
        # print hang,lie,i,j
        dp[i][j]=nums[i]

        for i in range(0,hang-1):

            dp[hang-2-i][0]=dp[hang-1-i][0]
            dp[hang-2-i][1]=dp[hang-1-i][1]
            dp[hang-2-i][2]=dp[hang-1-i][2]

            t1=nums[hang-2-i]%3
            dp[hang-2-i][t1]=max(nums[hang-2-i],dp[hang-1-i][t1],dp[hang-2-i][t1])

            t2=(dp[hang-1-i][0]+nums[hang-2-i])%3
            dp[hang-2-i][t2]=max(dp[hang-1-i][0]+nums[hang-2-i],dp[hang-1-i][t2],dp[hang-2-i][t2])

            t3=(dp[hang-1-i][1]+nums[hang-2-i])%3
            dp[hang-2-i][t3]=max(dp[hang-1-i][1]+nums[hang-2-i],dp[hang-1-i][t3],dp[hang-2-i][t3])

            t4=(dp[hang-1-i][2]+nums[hang-2-i])%3
            dp[hang-2-i][t4]=max(dp[hang-1-i][2]+nums[hang-2-i],dp[hang-1-i][t4],dp[hang-2-i][t4])        

        # print dp 
        return dp[0][0]