Given an array nums of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.


 
Example 1:
Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).
Example 2:
Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.

Example 3:
Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).

 
Constraints:

1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4

Difficulty: interview

Starter code:

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        

Solutions:
#5:09
'''
nums = [3,6,5,1,8]
sum_nums = 23
mod3_sum_nums = 2
mod3_dict = {0:[3,6], 1:[1], 2:[5,8]}
helper([5,8], [1]) -> 5





'''

from collections import defaultdict
class Solution:
    def helper(self, l1, l2):
        if len(l1) < 1 and len(l2) <2:
            sum_remove = 0
        elif len(l1) < 1:
            sum_remove = min(l2)
            l2.remove(sum_remove)
            sum_remove += min(l2)
            
        elif len(l2) <2:
            sum_remove = min(l1)
            
        else:
            sum_remove1 = min(l1)
            sum_remove2 = min(l2)
            l2.remove(sum_remove2)
            sum_remove2 += min(l2)
            sum_remove = min(sum_remove1, sum_remove2)
        
        return sum_remove
            
            
    def maxSumDivThree(self, nums: List[int]) -> int:
        sum_nums = sum(nums)
        mod3_sum_nums = sum_nums%3
        if mod3_sum_nums == 0:
            return sum_nums
        
        mod3_dict = defaultdict(list)
        for i,num in enumerate(nums):
            mod3_dict[num%3].append(num)
         
        
        if mod3_sum_nums ==1:
            sum_remove = self.helper(mod3_dict[1], mod3_dict[2])
            
        else:
            sum_remove = self.helper(mod3_dict[2], mod3_dict[1])
        
        if sum_remove >0:
            return sum_nums - sum_remove
        else:
            return 0
            
        


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        if sum(nums) % 3 == 0:
            return sum(nums)
        
        mod1 = [num for num in nums if num % 3 == 1]
        mod2 = [num for num in nums if num % 3 == 2]
        mod1_min = min(mod1 or [float('inf')])
        mod2_min = min(mod2 or [float('inf')])
        
        if mod1_min != float('inf'):
            mod1.remove(mod1_min)
        
        if mod2_min != float('inf'):
            mod2.remove(mod2_min)
        
        possibilities = [ 
            sum(nums) - mod1_min,
            sum(nums) - mod2_min,
            sum(nums) - mod1_min - min(mod1 or [float('inf')]),
            sum(nums) - mod2_min - min(mod2 or [float('inf')]),
        ]
        
        
        
        return max([
            pos for pos in possibilities if pos % 3 == 0
        ] or [0])


# 1262. Greatest Sum Divisible by Three

# Explanation: seen[i] means the current maximum possible sum that sum % 3 = i
# Complexity: Time O(N), Space O(1)

class Solution1:
    def maxSumDivThree(self, nums: List[int]) -> int:
        seen = [0, 0, 0]
        for a in nums:
            for i in seen[:]: # 这里必须用 [:] 否则 下一次迭代会使用更新后的值 计算结果不对
                seen[(i + a) % 3] = max(seen[(i + a) % 3], i + a)
                # print(a, i, seen)
        return seen[0]
    
# Divide the whole list into three parts: mod_0, mod_1, mod_2.
# Think about the sum of the original list, if it mods 3 == 0, then we can just return the sum.
# If tot_sum % 3 == 1, then we should remove one smallest element from mod_1 or two smallest ones from mod_2.
# If tot_sum % 3 == 2, then we should remove one smallest element from mod_2 or two smallest ones from mod_1.

class Solution: # （没明白。。）
    def maxSumDivThree(self, nums: List[int]) -> int:
        mod_1, mod_2,res,remove = [], [], 0, float('inf')
        for i in nums:
            if i % 3 == 0: res += i
            if i % 3 == 1: mod_1 += [i]
            if i % 3 == 2: mod_2 += [i]
        mod_1.sort(reverse = True)
        mod_2.sort(reverse = True)
        tmp = sum(mod_1) + sum(mod_2)
        if tmp % 3 == 0:
            return res + tmp
        elif tmp% 3 == 1:
            if len(mod_1): 
                remove = min(remove, mod_1[-1])
            if len(mod_2) > 1: 
                remove = min(mod_2[-1] + mod_2[-2], remove)
        elif tmp % 3 == 2:
            if len(mod_2): 
                remove = min(remove, mod_2[-1])
            if len(mod_1) > 1: 
                remove = min(mod_1[-1] + mod_1[-2], remove)
        return res + tmp - remove

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        dp = [ [0 for _ in range(3)] for _ in range(len(nums))]
        dp[0][nums[0]%3] = nums[0]
        for i in range(1, len(nums)):
            for j in range(3):
                dp[i][j] = dp[i-1][j]
            currNum = nums[i]
            for j in range(3):
                curr = dp[i-1][j] + nums[i]
                k = curr %3
                dp[i][k] = max(dp[i][k], curr)
        return dp[len(nums)-1][0]


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

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        n = len(nums)
        zero, one, two = [0]*(n+1),[0]*(n+1),[0]*(n+1)
        one[0] = two[0] = float('-inf')
        for i in range(1,n+1):
            if nums[i-1]%3 == 0:
                zero[i] = zero[i-1]+nums[i-1]
                one[i] = one[i-1]+nums[i-1] if one[i-1]>0 else 0
                two[i] = two[i-1]+nums[i-1] if two[i-1]>0 else 0
            elif nums[i-1]%3 == 1:
                zero[i] = max(two[i-1]+nums[i-1],zero[i-1])
                two[i] = max(two[i-1],one[i-1]+nums[i-1])
                one[i] = max(one[i-1],zero[i-1]+nums[i-1])
            else:
                zero[i] = max(one[i-1]+nums[i-1],zero[i-1])
                two[i] = max(zero[i-1]+nums[i-1],two[i-1])
                one[i] = max(two[i-1]+nums[i-1],one[i-1])
        return zero[-1]

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


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dp = [[0, -1, -1] for _ in range(len(nums)+1)]
        for i in range(1, len(nums)+1):
            r = nums[i-1] % 3
            for s in range(3):
                if dp[i-1][s] >= 0:
                    dp[i][(r+s)%3] = max(dp[i-1][(r+s)%3], dp[i-1][s]+nums[i-1])
                dp[i][s] = max(dp[i-1][s], dp[i][s])
        
        return dp[len(nums)][0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        m = sum(nums)
        N = len(nums)
        
        @lru_cache(None)
        def dp(i,p): # best sumsofar at i
            if i == N:
                return 0 if p == 0 else -float('inf') 
            
            a = dp(i+1, p)
            b = dp(i+1, (p+nums[i])%3)+nums[i]
            return max(a,b)
        
        return dp(0,0)

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

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        
        n = len(nums)
        dp = [[0]*3 for _ in range(n)]
        
        for i, x in enumerate(nums):
            m = x % 3
            if i > 0:
                dp[i] = dp[i-1][::]
                # for j in range(3):
                #     if dp[i][(j-m)%3] > 0:
                #         dp[i][j] = max(dp[i][j], dp[i][(x-m)%3] + x)
                rot = [dp[i][(x-m)%3] for x in range(3)]

                for j in range(3):
                    if rot[j] > 0:
                        dp[i][j] = max(dp[i][j], rot[j] + x) # can add to it
                        
            dp[i][m] = max(dp[i][m], x) # better to start anew with current element
            
                
        print(dp)
        return dp[-1][0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:        
        dp=[[0]*3 for i in range(len(nums))]
        for i in range(len(dp)):
            dp[i]=list(dp[i-1])
            for k in range(3):
                index=((dp[i-1][k] if i-1>=0 else 0)+nums[i])%3
                dp[i][index]=max((dp[i-1][k] if i-1>=0 else 0)+nums[i],dp[i][index])
        return dp[-1][0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        # dp 0/1 problem
        dp = [ [-float('inf')] * len(nums) for _ in range(3)]
        
        for i, n in enumerate(nums):
            if i == 0:
                dp[n%3][0] = n
            
            else:
                for rem in range(3):
                    # choose / don't choose
                    dp[(n+rem)%3][i] = max(dp[rem][i-1] + n, dp[(n+rem)%3][i-1]) 
                # how about just n itself
                dp[n%3][i] = max(n, dp[n%3][i])
          

        return dp[0][-1] if dp[0][-1] != -float('inf') else 0
 


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


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

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        memo = {}
        self.helper(0,nums,memo)
        return memo[(0,0)]
        
    def helper(self,index,nums,memo):
        if index == len(nums):
            memo[(index,0)] = 0
            memo[(index,1)] = 0
            memo[(index,2)] = 0
        else:
            self.helper(index + 1,nums,memo)
            for i in range (3):
                if (i != 0) and (memo[(index + 1, i)] == 0):
                    memo[(index,(i + nums[index]) % 3)] = max(0,memo[(index + 1,(i + nums[index]) % 3)])
                else:
                    new_mod = (nums[index] + memo[(index + 1, i)]) % 3
                    new_sum = max(nums[index] + memo[(index + 1,i)],memo[(index + 1,new_mod)])
                    memo[(index,new_mod)] = new_sum
            return






class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        
        res = 0
        total = sum(nums)
        
        #only consider removing numbers that are not already divisible by 3
        remove = tuple(sorted(n for n in nums if n%3))
        
        q = collections.deque([(total, 0)]) #total and bitmasked removed numbers
        visited = set([0])
        
        while q:
            
            t, r = q.popleft()
            
            if not t%3:
                res = max(res, t)
                continue

            if t <= res:
                continue

            for i in range(len(remove)):
                if not (1 << i) & r:
                    b = (1 << i) | r
                    if b not in visited:
                        visited.add(b)
                        q.append((t-remove[i], b))
        
        return res

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        snum = sum(nums)
        if not snum%3: return snum
        ones, twos = [], []
        nums.sort()
        for k, v in enumerate(nums):
            if v%3 == 1: 
                ones += [nums[k]] 
            if v%3 == 2:
                twos += [nums[k]]
        if snum%3 == 1:
            snum = max(snum - ones[0], snum - sum(twos[:2])) if len(twos) >=2 else snum - ones[0]
        if snum%3 == 2:
            snum = max(snum - twos[0], snum - sum(ones[:2])) if len(ones) >=2 else snum - twos[0]
        return snum
        
        


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        #nums=[2,6,2,2,7]
        nums.sort()
        
        quotient = []   # *3
        remainder = []
        ret = 0
        
        for num in nums:
            quotient.append(num//3*3)
            remainder.append(num%3)
            ret += num
        
        #print(nums)
        #print(quotient)
        #print(remainder)
        
        remainder_sum = ret%3
        #print(remainder_sum)
        if remainder_sum == 0:
            return ret
        elif remainder_sum == 1:
            # compare min remainder 1 and 2
            remainder1 = 0
            remainder1_count = 0
            remainder2 = 0
            remainder2_count = 0
            for i in range(len(nums)):
                if remainder[i] == 1:
                    if remainder1_count >= 1:
                        continue
                    remainder1_count += 1
                    remainder1 += nums[i]
                if remainder[i] == 2:
                    if remainder2_count >= 2:
                        continue
                    remainder2_count += 1
                    remainder2 += nums[i]    
                if remainder2_count >= 1 and remainder1_count >= 2:
                    break
                
            if remainder2_count == 2 and remainder1_count == 1:
                return ret - min(remainder1, remainder2)
            elif remainder2_count == 2:
                return ret - remainder2
            elif remainder1_count == 1:
                return ret - remainder1
            else:
                return 0
        else:
            # compare min remainder 1 and 2
            remainder1 = 0
            remainder1_count = 0
            remainder2 = 0
            remainder2_count = 0
            for i in range(len(nums)):
                if remainder[i] == 1:
                    if remainder1_count >= 2:
                        continue
                    remainder1_count += 1
                    remainder1 += nums[i]
                if remainder[i] == 2:
                    if remainder2_count >= 1:
                        continue
                    remainder2_count += 1
                    remainder2 += nums[i]    
                if remainder2_count >= 1 and remainder1_count >= 2:
                    break
                
            if remainder2_count == 1 and remainder1_count == 2:
                return ret - min(remainder1, remainder2)
            elif remainder2_count == 1:
                return ret - remainder2
            elif remainder1_count == 2:
                return ret - remainder1
            else:
                return 0
                
            return 0
            
        return 0

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        mod_one = [-1, -1]
        mod_two = [-1, -1]
        total_sum = 0
        for x in nums:
            total_sum += x
            if x % 3 == 1:
                if mod_one[0] == -1 or x < mod_one[0]:
                    mod_one[1] = mod_one[0]
                    mod_one[0] = x
                elif mod_one[1] == -1 or x < mod_one[1]:
                    mod_one[1] = x
            elif x % 3 == 2:
                if mod_two[0] == -1 or x < mod_two[0]:
                    mod_two[1] = mod_two[0]
                    mod_two[0] = x
                elif mod_two[1] == -1 or x < mod_two[1]:
                    mod_two[1] = x
        
        if total_sum % 3 == 0:
            return total_sum
        elif total_sum % 3 == 1:
            if mod_one[0] != -1 and (mod_two[0] == -1 or mod_two[1] == -1 or mod_one[0] < sum(mod_two)):
                return total_sum - mod_one[0]
            elif mod_two[0] != -1 and mod_two[1] != -1:
                return total_sum - sum(mod_two)
            else:
                return 0
        else:
            if mod_two[0] != -1 and (mod_one[0] == -1 or mod_one[1] == -1 or mod_two[0] < sum(mod_one)):
                return total_sum - mod_two[0]
            elif mod_one[0] != -1 and mod_one[1] != -1:
                return total_sum - sum(mod_one)
            else:
                return 0

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        mod_1, mod_2,res,remove = [], [], 0, float('inf')
        for i in nums:
            if i%3 == 0: res += i
            if i%3 == 1: mod_1 += [i]
            if i %3 == 2: mod_2 += [i]
        mod_1.sort(reverse = True)
        mod_2.sort(reverse = True)
        tmp = sum(mod_1) +sum(mod_2)
        if tmp % 3 == 0:
            return res + tmp
        elif tmp% 3 == 1:
            if len(mod_1): remove = min(remove,mod_1[-1])
            if len(mod_2) > 1: remove = min(mod_2[-1]+mod_2[-2],remove)
        elif tmp % 3 == 2:
            if len(mod_2): remove = min(remove,mod_2[-1])
            if len(mod_1) > 1: remove = min(mod_1[-1]+mod_1[-2],remove)
        return res + tmp - remove
                



class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        mod_1, mod_2,res,remove = [], [], 0, float('inf')
        for i in nums:
            if i%3 == 0: res += i
            if i%3 == 1: mod_1 += [i]
            if i %3 == 2: mod_2 += [i]
        mod_1.sort(reverse = True)
        mod_2.sort(reverse = True)
        tmp = sum(mod_1) +sum(mod_2)
        if tmp % 3 == 0:
            return res + tmp
        elif tmp% 3 == 1:
            if len(mod_1): remove = min(remove,mod_1[-1])
            if len(mod_2) > 1: remove = min(mod_2[-1]+mod_2[-2],remove)
        elif tmp % 3 == 2:
            if len(mod_2): remove = min(remove,mod_2[-1])
            if len(mod_1) > 1: remove = min(mod_1[-1]+mod_1[-2],remove)
        return res + tmp - remove

def s(l1, l1_start_idx, l2, l2_start_idx):
    if len(l1) < l1_start_idx or len(l2) < l2_start_idx:
        return 0
    
    res = sum(l1[0:l1_start_idx]) + sum(l2[0:l2_start_idx])
    
    l1_end = l1_start_idx + 3 * ((len(l1) - l1_start_idx) // 3)
    res += sum(l1[l1_start_idx:l1_end])
    
    l2_end = l2_start_idx + 3 * ((len(l2) - l2_start_idx) // 3)
    res += sum(l2[l2_start_idx:l2_end])
    
    return res

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        res = 0
        ones = []
        twos = []
        for n in nums:
            mod = n % 3
            if mod == 0:
                res += n
            elif mod == 1:
                ones.append(n)
            elif mod == 2:
                twos.append(n)
        ones.sort(reverse = True)
        twos.sort(reverse = True)
        
        counter = 0
        ones_sum = [0]
        for x in ones:
            counter += x
            ones_sum.append(counter)
        
        counter = 0
        twos_sum = [0]
        for x in twos:
            counter += x
            twos_sum.append(counter)

        m = 0
        for i in range(0, min(len(ones), len(twos)) + 1):
            one_end = i + ((len(ones) - i) // 3 ) * 3
            two_end = i + ((len(twos) - i) // 3 ) * 3
            x = ones_sum[one_end] + twos_sum[two_end]
            m = max(m, x)
        
        res += m
            
        return res

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        nums = sorted(nums)
        l0 = [i for i in nums if i % 3 == 0]
        l1 = [i for i in nums if i % 3 == 1]
        l2 = [i for i in nums if i % 3 == 2]
        
        print((l0, l1, l2))
        
        total_sum = sum(nums)
        
        res = total_sum
        
        if total_sum % 3 != 0:
            
            if total_sum % 3 == 1:
                res1 = sum(l0) + sum(l1[1:]) + sum(l2)
                res2 = sum(l0) + sum(l1) + sum(l2[2:])

            elif total_sum % 3 == 2:
                res1 = sum(l0) + sum(l1[2:]) + sum(l2)
                res2 = sum(l0) + sum(l1) + sum(l2[1:])
            
            if res1 % 3 == 0 and res2%3 == 0:
                res = max(res1, res2)
            elif res1 % 3 == 0:
                res = res1
            else:
                res = res2
        
        return res


class Solution:
    def maxSumDivThree(self, nums):

        total =     sum(nums)
        mod_total = total % 3 

        if mod_total == 0:
            return total

        else:

            def min_n(nums, n):
                if len(nums) < n: return 10**6
                sum_n = 0
                for i in range(n):
                    min_current = min(nums)
                    min_current_ind = nums.index(min_current)
                    sum_n += nums.pop(min_current_ind)
                return sum_n

            mod_1 = [e for e in nums if e % 3 == 1]
            mod_2 = [e for e in nums if e % 3 == 2]

            if mod_total == 1:

                one_mod_1 =   min_n(mod_1, 1)
                two_mod_2 =   min_n(mod_2, 2)

                return total - min(one_mod_1, two_mod_2)

            elif mod_total == 2:

                two_mod_1 =   min_n(mod_1, 2)
                one_mod_2 =   min_n(mod_2, 1)

                return total - min(two_mod_1, one_mod_2)


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        m0 = 0
        m1 = 0
        m2 = 0
        for n in nums:
            m = n % 3
            m0n, m1n, m2n = m0, m1, m2
            
            if m == 0:
                m0n = m0 + n
                m1n = m1 + n
                m2n = m2 + n
            elif m == 1:
                if m2 % 3 == 2:
                    m0n = max(m0, m2 + n)
                m1n = max(m1, m0 + n)
                if m1 % 3 == 1:
                    m2n = max(m2, m1 + n)
            elif m == 2:
                if m1 % 3 == 1:
                    m0n = max(m0, m1 + n)
                if m2 % 3 == 2:
                    m1n = max(m1, m2 + n)
                m2n = max(m2, m0 + n)
            m0, m1, m2 = m0n, m1n, m2n
            
        return m0

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        counts = [0, 0, 0]
        small_two = []
        small_one = []

        result = 0
        for i in nums:
            result += i
            rem = i % 3
            counts[i % 3] += 1
            
            if rem == 0:
                continue
            elif rem == 1:
                small_one = sorted(small_one + [i])[:3]
            else:
                small_two = sorted(small_two + [i])[:3]

        # compensate
        print(small_two, small_one, result)
        if result % 3 == 2:
            return result - (small_two[0] if len(small_one) < 2 or (small_two[0] < small_one[0]+small_one[1]) else small_one[0]+small_one[1])
        if result % 3 == 1:
            return result - (small_one[0] if len(small_two) < 2 or (small_one[0] < small_two[0]+small_two[1]) else small_two[0]+small_two[1])

        return result

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        total = sum(nums)
        nums.sort()

        rest = total % 3

        if not rest:
            return total

        a, b = 0, 0
        for n in nums:
            if b and n > b:
                break

            mod = n % 3
            if mod:
                if rest == mod:
                    return total - n
                else:
                    if not a:
                        a = n
                    elif not b:
                         b = a + n

        return total - b

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        snum = sum(nums)
        nums.sort()
        if not snum%3: return snum
        ones, twos = [], []
        for k, v in enumerate(nums):
            if v%3 == 1: 
                heapq.heappush(ones,nums[k])
            if v%3 == 2:
                heapq.heappush(twos,nums[k])
        if snum % 3 == 1:
            snum = snum - min(ones[0], sum(twos[:2])) if len(twos) >=2 else snum - ones[0]
        if snum % 3 == 2:
            snum = snum - min(twos[0], sum(ones[:2])) if len(ones) >= 2 else snum - twos[0]
        return snum
        
        


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        x=sum(nums)
        if x%3==0:
            return x
        nums.sort()
        opt1=10**4+1
        opt2=count=0
        for n in nums:
            if n%3==x%3:
                opt1=min(opt1, n)
                if count==2:
                    break
            elif n%3!=0 and n%3!=x%3:
                if count<=1:
                    opt2+=n
                    count+=1
                if count==2 and opt1<10**4+1:
                    break
        if count==2:
            return x-min(opt1,opt2)
        return x-opt1

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        total = sum(nums)
        n = len(nums)
        if total%3 == 0:
            return total
        nums_set = set(nums)
        div, mod = divmod(total, 3)
        nums.sort()
        while mod <= total:
            if mod in nums_set:
                return div*3
            for i in range(n-2):
                sum_val = 0
                if nums[i] > mod:
                    break
                for j in range(i+1, n-1):
                    if nums[i] + nums[j] == mod:
                        return div*3    
                    for k in range(j+1, n):
                        #print(i, j, k)
                        #print(nums[i], nums[j:k])
                        sum_val += nums[i] + sum(nums[j:k])
                        if sum_val == mod:
                            return div*3
                        if sum_val > mod:
                            break     

            div -= 1
            mod += 3

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dp = [0, None, None]
        for num in nums:
            mod = num % 3 
            if mod == 0:
                dp[0], dp[1], dp[2] = (dp[0] + num, 
                                       dp[1] + num if dp[1] else None, 
                                       dp[2] + num if dp[2] else None)
            elif mod == 1:
                dp[0], dp[1], dp[2] = (max(dp[0], dp[2] + num if dp[2] else 0),
                                       max(dp[1] if dp[1] else 0, dp[0] + num),
                                       max(dp[2] if dp[2] else 0, dp[1] + num if dp[1] else 0) if dp[1] or dp[2] else None)
            elif mod == 2:
                dp[0], dp[1], dp[2] = (max(dp[0], dp[1] + num if dp[1] else 0),
                                       max(dp[1] if dp[1] else 0, dp[2] + num if dp[2] else 0) if dp[1] or dp[2] else None,
                                       max(dp[2] if dp[2] else 0, dp[0] + num))
        return dp[0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        x=sum(nums)
        if x%3==0:
            return x
        nums.sort()
        #print(nums,x)
        opt1=10**4+1
        opt2=count=0
        for n in nums:
            if n%3==x%3:
                opt1=min(opt1, n)
                if count==2:
                    break
            elif n%3!=0 and n%3!=x%3:
                if count<=1:
                    opt2+=n
                    count+=1
                elif count==2:
                    pass
        #print(opt1, opt2)
        if count==2:
            return x-min(opt1,opt2)
        return x-opt1

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dp = [0, 0, 0]
        for n in nums:
            if n % 3 == 0:
                dp0 = dp[0] + n
                if dp[1] > 0: dp1 = dp[1] + n
                else: dp1 = dp[1]
                if dp[2] > 0: dp2 = dp[2] + n
                else: dp2 = dp[2]
            elif n % 3 == 1:
                if dp[2] > 0: dp0 = max(dp[0], dp[2] + n)
                else: dp0 = dp[0]
                if dp[0] > 0: dp1 = max(dp[1], dp[0] + n)
                else: dp1 = max(dp[1], n) 
                if dp[1] > 0: dp2 = max(dp[2], dp[1] + n)
                else: dp2 = dp[2]
            elif n % 3 == 2:
                if dp[1] > 0: dp0 = max(dp[0], dp[1] + n)
                else: dp0 = dp[0]
                if dp[2] > 0: dp1 = max(dp[1], dp[2] + n)
                else: dp1 = dp[1]
                if dp[0] > 0: dp2 = max(dp[2], dp[0] + n)
                else: dp2 = max(dp[2], n)
            dp[0] = dp0
            dp[1] = dp1
            dp[2] = dp2
            

        return dp[0]


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        r0, r1, r2 = 0, 0, 0
        for val in nums:
            r = val % 3
            if r == 0:
                new_r0 = r0 + val
                new_r1 = r1 + val if r1 else 0
                new_r2 = r2 + val if r2 else 0
            elif r == 1:
                new_r0 = max(r2 + val, r0) if r2 else r0
                new_r1 = max(r0 + val, r1)
                new_r2 = max(r1 + val, r2) if r1 else r2
            elif r == 2:
                new_r0 = max(r1 + val, r0) if r1 else r0
                new_r1 = max(r2 + val, r1) if r2 else r1
                new_r2 = max(r0 + val, r2) 
                
            r0, r1, r2 = new_r0, new_r1, new_r2
        
        return r0


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        S = sum(nums)
        if S%3==0: return S
        
        ns1 = sorted([n for n in nums if n%3==1])
        ns2 = sorted([n for n in nums if n%3==2])
        
        remove = S
        
        if ([[],ns1,ns2][S%3]):
            remove = min(remove, [[],ns1,ns2][S%3][0])
        if len([[],ns1,ns2][3-S%3])>1:
            remove = min(remove, sum([[],ns1,ns2][3-S%3][:2]))
        
        return S - remove

import heapq
from collections import defaultdict, Counter
class Solution:
    '''Return the smallest / 2nd smallest element'''
    def get_min_1_2(self, nums):
        return heapq.nsmallest(2, nums)
    
    def maxSumDivThree(self, nums: List[int]) -> int:
        sum_ = sum(nums)
        mod_dic = defaultdict(list)    # Hash table: 1->[1, 7, 10...]
        for num in nums:
            mod_dic[num%3].append(num)
        print(mod_dic)
            
        if sum_%3 == 0:
            return sum_
        
        if sum_%3 == 1:
            sum1 = -float('inf')
            sum2 = -float('inf')
            if 1 in mod_dic:
                sum1 = sum_ - min(mod_dic[1])
            if 2 in mod_dic and len(mod_dic[2]) >= 2:
                min_mod2, second_min_mod2 = self.get_min_1_2(mod_dic[2])
                # min_mod2 = min(mod_dic[2])
                # mod_dic[2].remove(min_mod2)
                # second_min_mod2 = min(mod_dic[2])
                sum2 = sum_ - min_mod2 - second_min_mod2
            return max(sum1, sum2)
        
        if sum_%3 == 2:
            sum1 = -float('inf')
            sum2 = -float('inf')
            if 2 in mod_dic:
                sum2 = sum_ - min(mod_dic[2])
            if 1 in mod_dic and len(mod_dic[1]) >= 2:
                min_mod1, second_min_mod1 = self.get_min_1_2(mod_dic[1])
                # min_mod1 = min(mod_dic[1])
                # mod_dic[1].remove(min_mod1)
                # second_min_mod1 = min(mod_dic[1])
                sum1 = sum_ - min_mod1 - second_min_mod1
            return max(sum1, sum2)


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


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0,float('-inf'),float('-inf')] # largest number with remainder 0,1,2
        for i in range(1,n+1):
            x = nums[i-1]
            dp1 = [0]*3
            if x%3==0:
                for j in range(3):
                    dp1[j] = dp[j]+x
            elif x%3==1:
                dp1[0] = max(dp[0],dp[2]+x)
                dp1[1] = max(dp[1],dp[0]+x)
                dp1[2] = max(dp[2],dp[1]+x)
            elif x%3==2:
                dp1[0] = max(dp[0],dp[1]+x)
                dp1[1] = max(dp[1],dp[2]+x)
                dp1[2] = max(dp[2],dp[0]+x)
            dp=dp1
        return dp[0]


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        '''
        - Dynamic programming solution
        - We don't need to keep track of all sums, only of the 
          max sum for each possible remainder (0, 1, 2)
        
        
        '''
        
        max_sums = [0]*3
        
        for num in nums:
            for max_sum in max_sums[:]:
                max_sums[(num+max_sum)%3] = max(max_sum+num, max_sums[(num+max_sum)%3])
        
        return max_sums[0]


# 1262. Greatest Sum Divisible by Three

# Explanation: seen[i] means the current maximum possible sum that sum % 3 = i
# Complexity: Time O(N), Space O(1)

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


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


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

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

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        
        # n = len(nums)
        # # dp = [[0]*3 for _ in range(n)]
        # dp = [0,0,0]
        
#         for i, x in enumerate(nums):
#             m = x % 3
#             if i > 0:
#                 # dp[i] = dp[i-1][::]
#                 # for j in range(3):
#                 #     if dp[i][(j-m)%3] > 0:
#                 #         dp[i][j] = max(dp[i][j], dp[i][(x-m)%3] + x)
#                 rot = [dp[(x-m)%3] for x in range(3)]

#                 for j in range(3):
#                     if rot[j] > 0:
#                         dp[j] = max(dp[j], rot[j] + x) # can add to it
                        
#             dp[m] = max(dp[m], x) # better to start anew with current element
#             # print(i, dp)
                
#         # print(dp)
#         return dp[0]

        seen = [0,0,0]
        for a in nums:
            for i in seen[:]:
                seen[(i+a)%3] = max(seen[(i+a)%3], i+a)
                
            # print(a, seen)
            
        return seen[0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        total = sum(nums)
        mod = total % 3
        if mod == 0:
            return total
        min_2 = defaultdict(list)
        for num in nums:
            if num % 3 == 1:
                min_2[1].append(num)
                min_2[1].sort()
                if len(min_2[1]) > 2:
                     min_2[1].pop()
            elif num % 3 == 2:
                min_2[2].append(num)
                min_2[2].sort()
                if len(min_2[2]) > 2:
                     min_2[2].pop()
        res = 0
        if mod == 1:
            if len(min_2[1]) >= 1:
                res = total - min_2[1][0]
            if len(min_2[2]) >= 2:
                res = max(res, total - min_2[2][0] - min_2[2][1])
            return res
        if len(min_2[2]) >= 1:
            res = total - min_2[2][0]
        if len(min_2[1]) >= 2:
            res = max(res, total - min_2[1][0] - min_2[1][1])
        return res

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


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dp=[0,0,0]
        for num in nums:
            newlist=dp.copy()
            for i in range(len(dp)):
                curr=newlist[i]+num
                dp[curr%3]=max(dp[curr%3],curr)
        return dp[0]

class Solution:
    # https://leetcode.com/problems/greatest-sum-divisible-by-three/discuss/431077/JavaC%2B%2BPython-One-Pass-O(1)-space
    def maxSumDivThree(self, nums: List[int]) -> int:
        seen = [0, 0, 0]
        for n in nums:
            # we need create a copy of seen, since we change element of seen in for loop.
            for j in [i + n for i in seen]:
                seen[j % 3] = max(seen[j % 3], j)
        return seen[0]

class Solution:
    # https://leetcode.com/problems/greatest-sum-divisible-by-three/discuss/431077/JavaC%2B%2BPython-One-Pass-O(1)-space
    def maxSumDivThree(self, nums: List[int]) -> int:
        seen = [0, 0, 0]
        for n in nums:
            # we need create a copy of seen, since we change element of seen in for loop.
            for j in [i + n for i in seen]:
                seen[j % 3] = max(seen[j % 3], j)
            # print('n = {0}, seen = {1}'.format(n, seen))
        return seen[0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dp = [0] * 3
        
        for num in nums:
            r = num % 3
            
            pre = dp[:]
            for i in range(3):
                if pre[i]:
                    dp[(i + r) % 3] = max(pre[(i + r) % 3], pre[i] + num)
                    
            if dp[r] == 0:
                dp[r] = num
                
        return dp[0]


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        cur = [0] + [-1] * 2
        tmp = cur[:]
        for x in nums:
            for i in range(3):
                idx = (i+x)%3
                if cur[i] >= 0:
                    tmp[idx] = max(cur[i] + x, cur[idx])
                    
            cur = tmp[:]
        return cur[0]

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


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [ [0]*(3) for _ in range(n+1)  ]
        dp[0] = [0,float('-inf'),float('-inf')] # largest number with remainder 0,1,2
        for i in range(1,n+1):
            x = nums[i-1]
            if x%3==0:
                for j in range(3):
                    dp[i][j] = dp[i-1][j]+x
            elif x%3==1:
                dp[i][0] = max(dp[i-1][0],dp[i-1][2]+x)
                dp[i][1] = max(dp[i-1][1],dp[i-1][0]+x)
                dp[i][2] = max(dp[i-1][2],dp[i-1][1]+x)
            elif x%3==2:
                dp[i][0] = max(dp[i-1][0],dp[i-1][1]+x)
                dp[i][1] = max(dp[i-1][1],dp[i-1][2]+x)
                dp[i][2] = max(dp[i-1][2],dp[i-1][0]+x)
        return dp[n][0]


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        sumVal = sum(nums)
        if sumVal % 3 == 0:
            return sumVal
        categories = [[],[],[]]
        for num in nums:
            categories[num % 3].append(num)
        categories[1].sort()
        categories[2].sort()
        if sumVal % 3 == 1:
            if (len(categories[2]) < 2):
                return sumVal - categories[1][0]
            elif not categories[1]:
                return sumVal - categories[2][0] - categories[2][1]
            else:
                remainder = min(categories[1][0], categories[2][0] + categories[2][1])
                return sumVal - remainder
        else:
            if (len(categories[1]) < 2):
                return sumVal - categories[2][0]
            elif not categories[2]:
                return sumVal - categories[1][0] - categories[1][1]
            else:
                remainder = min(categories[2][0], categories[1][0] + categories[1][1])
                return sumVal - remainder


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dp = [0] * 3
        
        for num in nums:
            r = num % 3
            
            pre = dp[:]
            for i in range(3):
                if pre[i]:
                    dp[(i + r) % 3] = max(pre[(i + r) % 3], pre[i] + num)
                    
            if not dp[r]:
                dp[r] = num
                
        return dp[0]


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


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        
        
        n = len(nums)+1
        
        dp = [[0]*3 for i in range(n)]
        
        dp[0][0], dp[0][1], dp[0][2] = 0, -float('inf'), -float('inf')
        
        for i in range(1,n):
            
            rem = nums[i-1]%3
            
            if rem == 0:
                
                dp[i][0] = dp[i-1][0] + nums[i-1]
                dp[i][1] = dp[i-1][1] + nums[i-1]
                dp[i][2] = dp[i-1][2] + nums[i-1]
                
            elif rem == 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])
                
            else:
                
                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[-1][0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dp = [0, -1, -1]
        
        for v in nums:
            new_dp = list(dp)
            if dp[v%3] < 0:
                new_dp[v%3] = v
            for i in range(0,3):
                new_i = (i+v) % 3
                if dp[i] >= 0:
                    new_dp[new_i] = max(dp[new_i], dp[i] + v)
                    
            dp = new_dp
#            print(dp)

        return dp[0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        maxes = [0, 0, 0, 0]
        for num in nums:
            new_maxes = [x for x in maxes]
            for module in maxes:
                idx = (num + module) %3
                new_maxes[idx] = max(new_maxes[idx], num+module)
            maxes = new_maxes
        return maxes[0]
                


class Solution:
    def maxSumDivThree(self, A):
        print(A)
        seen = [0, 0, 0]
        for a in A:
            temp = seen.copy()
            for i in seen:            
                temp[(i + a) % 3] = max(temp[(i + a) % 3], i + a)
            seen = temp

        return seen[0]

class Solution:
    def maxSumDivThree(self, A):
        seen = [0,0,0]
        for a in A:
            for i in seen:
                temp = seen.copy()
                temp[(i+a)%3] = max(temp[(i+a)%3], i+a)
                seen = temp
        return seen[0]

import heapq
from collections import defaultdict, Counter
class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        sum_ = sum(nums)
        mod_dic = defaultdict(list)    # Hash table: 1->[1, 7, 10...]
        for num in nums:
            mod_dic[num%3].append(num)
        print(mod_dic)
            
        if sum_%3 == 0:
            return sum_
        
        if sum_%3 == 1:
            sum1 = -float('inf')
            sum2 = -float('inf')
            if 1 in mod_dic:
                sum1 = sum_ - min(mod_dic[1])
            if 2 in mod_dic and len(mod_dic[2]) >= 2:
                min_mod2, second_min_mod2 = heapq.nsmallest(2, mod_dic[2])
                sum2 = sum_ - min_mod2 - second_min_mod2
            return max(sum1, sum2)
        
        if sum_%3 == 2:
            sum1 = -float('inf')
            sum2 = -float('inf')
            if 2 in mod_dic:
                sum2 = sum_ - min(mod_dic[2])
            if 1 in mod_dic and len(mod_dic[1]) >= 2:
                min_mod1, second_min_mod1 = heapq.nsmallest(2, mod_dic[1])
                sum1 = sum_ - min_mod1 - second_min_mod1
            return max(sum1, sum2)


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        total = sum(nums)
        n = len(nums)
        if total%3 == 0:
            return total
        nums_set = set(nums)
        nums.sort()
        prefix_sum = [0] * (n+1)
        for i in range(n):
            prefix_sum[i] = prefix_sum[i-1] + nums[i] 
        div, mod = divmod(total, 3)    
        while mod <= total:
            if mod in nums_set:
                return div*3
            for i in range(n-2):
                sum_val = 0
                if nums[i] > mod:
                    break
                for j in range(i+1, n-1):
                    if nums[i] + nums[j] == mod:
                        return div*3    
                    for k in range(j+1, n):
                        sum_val += prefix_sum[k] - prefix_sum[i-1]
                        if sum_val == mod:
                            return div*3
                        if sum_val > mod:
                            break    
            div -= 1
            mod += 3


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        n = len(nums)
        s = sum(nums)
        if s % 3 == 0:
            return s
        pos_1_1, pos_2_1 = True, True
        min_1_1, min_1_2, min_2_1, min_2_2 = float('inf'), float('inf'), float('inf'), float('inf')
        for i in range(n):
            if nums[i] % 3 == 1:
                if nums[i] < min_1_1:
                    min_1_1 = nums[i]
                    pos_1_1 = i
            elif nums[i] % 3 == 2:
                if nums[i] < min_2_1:
                    min_2_1 = nums[i]
                    pos_2_1 = i
        for i in range(n):
            if i == pos_1_1 or i == pos_2_1:
                continue
            if nums[i] % 3 == 1:
                min_1_2 = min(min_1_2, nums[i])
            if nums[i] % 3 == 2:
                min_2_2 = min(min_2_2, nums[i])
                
        if s % 3 == 1:
            return s - min(min_1_1, min_2_1 + min_2_2)
        return s - min(min_2_1, min_1_1 + min_1_2)
                
        
                
                
                
        
                
                
            


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        dp = [[0 for _ in range(3)] for _ in range(len(nums)+1)]
        dp[0][1] = float('-inf')
        dp[0][2] = float('-inf')
        
        for i in range(1, len(nums)+1):
            num = nums[i-1]
            rem = num % 3
            if rem == 0:
                dp[i][0] = max(dp[i-1][0], dp[i-1][0]+num)
                dp[i][1] = max(dp[i-1][1], dp[i-1][1]+num)
                dp[i][2] = max(dp[i-1][2], dp[i-1][2]+num)
            elif rem == 1:
                dp[i][0] = max(dp[i-1][0], dp[i-1][2]+num)
                dp[i][1] = max(dp[i-1][1], dp[i-1][0]+num)
                dp[i][2] = max(dp[i-1][2], dp[i-1][1]+num)
            else:
                dp[i][0] = max(dp[i-1][0], dp[i-1][1]+num)
                dp[i][1] = max(dp[i-1][1], dp[i-1][2]+num)
                dp[i][2] = max(dp[i-1][2], dp[i-1][0]+num)
        
        return dp[-1][0]

from collections import defaultdict

class Solution:
  def maxSumDivThree(self, nums: List[int]) -> int:
    dp = defaultdict(lambda: [0, float('-inf'), float('-inf')])
    
    for i, x in enumerate(nums):
      # print(i, x, dp[i-1][0], dp[i-1][2] + x)
      if x % 3 == 0:
        dp[i][0] = dp[i-1][0] + x
        dp[i][1] = dp[i-1][1] + x
        dp[i][2] = dp[i-1][2] + x
        
      elif x % 3 == 1:
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] + x)
        dp[i][2] = max(dp[i-1][2], dp[i-1][1] + x)
        dp[i][0] = max(dp[i-1][0], dp[i-1][2] + x)
        
      elif x % 3 == 2:
        dp[i][2] = max(dp[i-1][2], dp[i-1][0] + x)
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] + x)
        dp[i][1] = max(dp[i-1][1], dp[i-1][2] + x)
      # print(dp[i])

    return dp[len(nums) - 1][0]
  


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
#         total_sum = sum(nums)
#         sorted_nums = sorted(nums)
#         print(sorted_nums)

#         if total_sum%3 == 0:
#             return total_sum
#         curr_max = 0
#         for i in range(length(sorted_nums)):
#             if (total_sum - sorted_nums[i]) %3 == 0:
#                 curr_max = (total_sum - sorted_nums[i])
            
#             if (total_sum - sorted_nums[i]) %3 == 0:
#                 curr_max = (total_sum - sorted_nums[i])
            
        dp = [0, float('-inf'), float('-inf')]
        for n in nums:
            dp = [max(dp[i], dp[(3 - n%3 + i)%3]+n) for i in range(3)]
        return dp[0]
        
            


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[0]*3 for _ in range(n+1)]
        dp[0][1] = float('-inf')
        dp[0][2] = float('-inf')
        
        print (dp)
        for i in range(1, n+1):
            if nums[i-1] % 3 == 0: # Current remainder == 0
                dp[i][0] = max(dp[i-1][0], dp[i-1][0] + nums[i-1]) # Current remainder is 0, so we add to dp[i-1][0] to keep the remainder 0
                dp[i][1] = max(dp[i-1][1], dp[i-1][1] + nums[i-1]) # Current remainder is 0, so we add to dp[i-1][1] to keep the remainder 1
                dp[i][2] = max(dp[i-1][2], dp[i-1][2] + nums[i-1]) # Current remainder is 0, so we add to dp[i-1][2] to keep the remainder 2
            elif nums[i-1] % 3 == 1: # Current remainder == 1
                dp[i][0] = max(dp[i-1][0], dp[i-1][2] + nums[i-1]) # Current remainder is 1, so we add to dp[i-1][2] to keep the remainder 0
                dp[i][1] = max(dp[i-1][1], dp[i-1][0] + nums[i-1]) # Current remainder is 1, so we add to dp[i-1][0] to keep the remainder 1
                dp[i][2] = max(dp[i-1][2], dp[i-1][1] + nums[i-1]) # Current remainder is 1, so we add to dp[i-1][1] to keep the remainder 2
            else: # Current remainder == 2
                dp[i][0] = max(dp[i-1][0], dp[i-1][1] + nums[i-1]) # Can you tell how this works now?
                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[-1][0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        n = len(nums)
        
        if n == 0:
            return 0
        
        nums.sort()
        
        m3 = []
        m2 = []
        m1 = []
        
        for i in nums:
            if i % 3 == 0:
                m3.append(i)
            elif i % 3 == 2:
                m2.append(i)
            elif i % 3 == 1:
                m1.append(i)
        
        # print(m1)
        # print(m2)
        # print(m3)
        
        
        total = sum(nums)
        if total % 3 == 0:
            return total
        elif total % 3 == 2:
            comp1 = 0
            comp2 = 0
            
            if len(m2) > 0:
                comp1 = total - m2[0]
            
            if len(m1) > 1:
                comp2 = total - m1[0] - m1[1]
                
            return max(comp1, comp2)
    
        elif total % 3 == 1: 
            comp1 = 0
            comp2 = 0
            
            if len(m1) > 0:
                comp1 = total - m1[0]
            
            if len(m2) > 1:
                comp2 = total - m2[0] - m2[1]
                
            return max(comp1, comp2)

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        n=len(nums)
        dp=[[0 for _ in range(3)] for _ in range(n)]
        ans=0
        
        if nums[0]%3==0:
            dp[0][0]=nums[0]
        elif nums[0]%3==1:
            dp[0][1]=nums[0]
        else:
            dp[0][2]=nums[0]
            
        for i in range(1, n):
            if nums[i]%3==0:
                dp[i][0]=dp[i-1][0]+nums[i]
                if dp[i-1][1]!=0:
                    dp[i][1]=dp[i-1][1]+nums[i]
                else:
                    dp[i][1]=dp[i-1][1]
                if dp[i-1][2]!=0:
                    dp[i][2]=dp[i-1][2]+nums[i]
                else:
                    dp[i][2]=dp[i-1][2]          
            elif nums[i]%3==1:
                dp[i][1]=max(dp[i-1][0]+nums[i], dp[i-1][1])
                if dp[i-1][2]!=0:
                    dp[i][0]=max(dp[i-1][0], dp[i-1][2]+nums[i])
                else:
                    dp[i][0]=dp[i-1][0]
                if dp[i-1][1]!=0:
                    dp[i][2]=max(dp[i-1][2], dp[i-1][1]+nums[i])
                else:
                    dp[i][2]=dp[i-1][2]
            else:
                dp[i][2]=max(dp[i-1][0]+nums[i], dp[i-1][2])
                if dp[i-1][1]!=0:
                    dp[i][0]=max(dp[i-1][0], dp[i-1][1]+nums[i])
                else:
                    dp[i][0]=dp[i-1][0]
                if  dp[i-1][2]!=0:
                    dp[i][1]=max(dp[i-1][1], dp[i-1][2]+nums[i])
                else:
                    dp[i][1]=dp[i-1][1]    
        # print(dp)
        return dp[n-1][0]
            
            


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        l = [0] * 3
        for i in nums:
            t = [0] * 3
            for j in l:
                t[(j+i)%3] = max(t[(j+i)%3], j+i)
            
            for g in range(3):
                l[g] = max(t[g], l[g])
                
        return l[0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dp = [[0] * 3 for _ in range(len(nums)+1)]
        dp[0][1] = float('-inf')
        dp[0][2] = float('-inf')
        
        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])
            else:
                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[-1][0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[0]*3 for _ in range(n+1)]
        dp[0][1] = float('-inf')
        dp[0][2] = float('-inf')
        for i in range(1, n+1):
            if nums[i-1] % 3 == 0: # Current remainder == 0
                dp[i][0] = max(dp[i-1][0], dp[i-1][0] + nums[i-1]) # Current remainder is 0, so we add to dp[i-1][0] to keep the remainder 0
                dp[i][1] = max(dp[i-1][1], dp[i-1][1] + nums[i-1]) # Current remainder is 0, so we add to dp[i-1][1] to keep the remainder 1
                dp[i][2] = max(dp[i-1][2], dp[i-1][2] + nums[i-1]) # Current remainder is 0, so we add to dp[i-1][2] to keep the remainder 2
            elif nums[i-1] % 3 == 1: # Current remainder == 1
                dp[i][0] = max(dp[i-1][0], dp[i-1][2] + nums[i-1]) # Current remainder is 1, so we add to dp[i-1][2] to keep the remainder 0
                dp[i][1] = max(dp[i-1][1], dp[i-1][0] + nums[i-1]) # Current remainder is 1, so we add to dp[i-1][0] to keep the remainder 1
                dp[i][2] = max(dp[i-1][2], dp[i-1][1] + nums[i-1]) # Current remainder is 1, so we add to dp[i-1][1] to keep the remainder 2
            else: # Current remainder == 2
                dp[i][0] = max(dp[i-1][0], dp[i-1][1] + nums[i-1]) # Can you tell how this works now?
                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[n][0]        

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        ans = 0
        next_nums = []
        nums1, nums2 = [], []
        nums.sort(reverse=True)
        for n in nums:
            val = n % 3
            if val == 0:
                ans += n
            elif val == 1:
                nums1.append(n)
            else:
                nums2.append(n)

        if len(nums1) < len(nums2):
            small = nums1
            big = nums2
        else:
            small = nums2
            big = nums1

        mod = (len(big) - len(small)) % 3
        val1, val2 = 0, 0
        if mod == 0:
            val1 = sum(big) + sum(small)
        else:
            val1 = sum(small) + sum(big[:-mod])
            if len(big) >= 3 and 3 - mod <= len(small):
                val2 = sum(small[:-(3 - mod)]) + sum(big)

        return ans + max(val1, val2)

    def traversal(self, nums1, nums2, idx1, idx2, curr_val, visited):
        if idx1 == len(nums1) and idx2 == len(nums2):
            return curr_val, True

        if (idx1, idx2, curr_val) in visited:
            return visited[(idx1, idx2, curr_val)], False

        if idx1 + 1 <= len(nums1) and idx2 + 1 <= len(nums2):
            val, ret = self.traversal(
                nums1,
                nums2,
                idx1 + 1,
                idx2 + 1,
                curr_val + nums1[idx1] + nums2[idx2],
                visited
            )
            if ret:
                return val, True
            max_val = max(max_val, val)

        max_val = curr_val
        if idx2 + 3 <= len(nums2):
            s = nums2[idx2] + nums2[idx2 + 1] + nums2[idx2 + 2]
            val, ret = self.traversal(
                nums1,
                nums2,
                idx1,
                idx2 + 3,
                curr_val + s,
                visited
            )
            if ret:
                return val, True
            max_val = max(max_val, val)

        if idx1 + 3 <= len(nums1):
            s = nums1[idx1] + nums1[idx1 + 1] + nums1[idx1 + 2]
            val, ret = self.traversal(
                nums1,
                nums2,
                idx1 + 3,
                idx2,
                curr_val + s,
                visited
            )
            if ret:
                return val, True
            max_val = max(max_val, val)

        visited[(idx1, idx2, curr_val)] = max_val
        return max_val, True


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dp = [0] * 3
        for num in nums:
            tmp = list(dp)
            for s in tmp:
                dp[(s + num) % 3] = max([dp[(s + num) % 3], s + num])
        return dp[0]


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

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        
        n = len(nums)
        # dp = [[0]*3 for _ in range(n)]
        dp = [0,0,0]
        
        for i, x in enumerate(nums):
            m = x % 3
            if i > 0:
                # dp[i] = dp[i-1][::]
                # for j in range(3):
                #     if dp[i][(j-m)%3] > 0:
                #         dp[i][j] = max(dp[i][j], dp[i][(x-m)%3] + x)
                rot = [dp[(x-m)%3] for x in range(3)]

                for j in range(3):
                    if rot[j] > 0:
                        dp[j] = max(dp[j], rot[j] + x) # can add to it
                        
            dp[m] = max(dp[m], x) # better to start anew with current element
            # print(i, dp)
                
        # print(dp)
        return dp[0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        n = len(nums)
        # dp = [[0 for j in range(3)] for i in range(n)]
        # dp[0][nums[0]%3] = nums[0]
        # for i in range(1, n):
        #     for j in range(3):
        #         dp[i][j] = dp[i-1][j]
        #         if (j-nums[i]) % 3 == 0:
        #             dp[i][j] = max(dp[i-1][(j-nums[i]) % 3] + nums[i], dp[i-1][j])
        #         else:
        #             if dp[i-1][(j-nums[i]) % 3] > 0:
        #                 dp[i][j] = max(dp[i-1][(j-nums[i]) % 3] + nums[i], dp[i-1][j])
        # # print([i[0] for i in dp])
        # # print([i[1] for i in dp])
        # # print([i[2] for i in dp])
        # return dp[n-1][0]
        
        dp = [[0 for j in range(3)] for i in range(n+1)]
        dp[0][0], dp[0][1], dp[0][2] = 0, -float('inf'), -float('inf')
        for i in range(1, n+1):
            for j in range(3):
                dp[i][j] = max(dp[i-1][(j-nums[i-1]) % 3] + nums[i-1], dp[i-1][j])
        # print([i[0] for i in dp])
        # print([i[1] for i in dp])
        # print([i[2] for i in dp])
        return dp[n][0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        
        seen = [0]*3
        for a in nums:
            for i in seen[:]:
                seen[(i + a) % 3] = max(seen[(i + a) % 3], i + a)
        return seen[0]
        
        
        
        
        '''
        3,6,5,1,8

        0 , 0 , 0 
        
        
        '''

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        n = len(nums)
        
        dp = [[0,0,0] for i in range(n)]
        
        dp[0][nums[0]%3] = nums[0]
        for i in range(1,n):
            dp[i][0] = dp[i-1][0]
            dp[i][1] = dp[i-1][1]
            dp[i][2] = dp[i-1][2]
            
            if nums[i]%3 == 0:
                dp[i][0] = max(dp[i][0], dp[i-1][0] + nums[i])
                if dp[i-1][1]:
                    dp[i][1] = max(dp[i][1], dp[i-1][1] + nums[i])
                if dp[i-1][2]:
                    dp[i][2] = max(dp[i][2], dp[i-1][2] + nums[i])
                    
            elif nums[i]%3 == 1:
                if dp[i-1][2]:
                    dp[i][0] = max(dp[i][0], dp[i-1][2] + nums[i])
                
                dp[i][1] = max(dp[i][1], dp[i-1][0] + nums[i])
                if dp[i-1][1]:
                    dp[i][2] = max(dp[i][2], dp[i-1][1] + nums[i])
            else:
                if dp[i-1][1]:
                    dp[i][0] = max(dp[i][0], dp[i-1][1] + nums[i])
                if dp[i-1][2]:
                    dp[i][1] = max(dp[i][1], dp[i-1][2] + nums[i])
                dp[i][2] = max(dp[i][2], dp[i-1][0] + nums[i])
            # print(i, dp[i])
        
        return dp[n-1][0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        f = [[0] * 3 for i in range(len(nums))]
        f[0][nums[0] % 3] = nums[0]
        for i in range(1, len(nums)):
            for j in range(3):
                include = f[i-1][(j - nums[i]) % 3] + nums[i]
                if include % 3 == j:
                    f[i][j] = max(f[i-1][j], include)
                else:
                    f[i][j] = f[i-1][j]
        return f[-1][0]

class Solution:
    def maxSumDivThree(self, nums):
        N = len(nums)
        dp = [[0]*3 for _ in range(2)]
        dp[0][nums[0]%3] = nums[0]
        for n in range(1, N):
            row = n%2
            alt = 1-row
            r = nums[n]%3
            for i in range(3):
                if dp[alt][i] > 0:
                    dp[row][(i+r)%3] = dp[alt][i] + nums[n]
            for i in range(3):
                dp[row][i] = max(dp[row][i], dp[alt][i])
            dp[row][r] = max(dp[row][r], nums[n])
        # for l in dp:
        #     print(l)
        return dp[1-N%2][0]


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        nums = sorted(nums)
        s = sum(nums)
        if s % 3 == 0:
            return s
        one = [x for x in nums if x%3 == 1]
        two = [x for x in nums if x%3 == 2]
        three = [x for x in nums if x%3 == 0]
        if s % 3 == 1:
            if one and len(two)>1:
                return s - min(one[0], sum(two[0:2]))
            if one:
                return s - one[0]
            return s - sum(two[0:2])
        if s % 3 == 2:
            if len(one)>1 and two:
                return s - min(sum(one[0:2]), two[0])
            if len(one)>1:
                return s - sum(one[0:2])
            return s - two[0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dp = [[0]*3 for _ in range(len(nums)+1)]        
        
        for i, n in enumerate(nums):
            r = n%3
            for j in range(3):
                if dp[i][j] > 0:
                    dp[i+1][(j+r)%3] = max(dp[i][j] + n, dp[i][(j+r)%3] )
                else:
                    dp[i+1][(j+r)%3] = dp[i][(j+r)%3]
            
            dp[i+1][r] = max(n,dp[i+1][r])
                    
        #print(dp)
                
        return dp[-1][0]
            
        
        
        



class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        nr = len(nums)
        dp = [[0] * 3 for _ in range(nr)]
        dp[0][nums[0] % 3] = nums[0]
        
        for i in range(1, nr):
            for j in range(3):
                dp[i][j] = dp[i-1][j]
                
            for j in range(3):
                new_num = dp[i-1][j] + nums[i]
                new_rem = new_num % 3
                
                if dp[i][new_rem] < new_num:
                    dp[i][new_rem] = new_num
        

        return dp[nr-1][0]
                    
                    
                
            
        
      
        
        
        


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        #
        # DP ----- 544 ms (25.55%) / 19 MB (27.94%)
        # Only consider three cases: residue is in [0, 1, 2]
        # Maintain the greatest sum with residue [0, 1, 2] divived by 3, respectively.
        # For each number, consider the result when adding it and check whether the sum increases or not.
        # ------------------------------------------------------------------------------------------------------------
        dic = {0: 0}
        
        for n in nums:
            dic_new = {}
            #  If add `n`, the temporary result is denoted by `dic_new`
            for i, s in dic.items():
                r = (i + n) % 3
                dic_new[r] = max(n + s, dic.get(r, 0))
            # Update `dict` by `dic_new`
            for i, s in dic_new.items():
                dic[i] = max(s, dic.get(i, 0))
                        
        return dic.get(0, 0)

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        mod = [0, -1, -1]
        mod[nums[0] % 3] = nums[0]
        
        for i in range(1, len(nums)):
            mod2 = list(mod)
            for j in range(3):
                if mod[j] != -1:
                    newSum = mod[j] + nums[i]
                    mod2[newSum % 3] = max(mod[newSum % 3], newSum)
            mod = mod2
        
        return mod[0] if mod[0] != -1 else 0
                    


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dic = [0, 0, 0]
        for i in nums:
            if i % 3 == 0:
                dic[0]+=i
                if dic[2] != 0:
                    dic[2]+=i
                if dic[1] != 0 :
                    dic[1]+=i
            elif i % 3 == 1:
                a,b,c = dic[0],dic[1],dic[2]
                dic[1] = max(a+i, dic[1])
                if b != 0:
                    dic[2] = max(b+i, dic[2])
                if c!=0:
                    dic[0] = max(c+i, dic[0] )
            elif i % 3 == 2:
                a,b,c = dic[0],dic[1],dic[2]
                dic[2] = max(a+i, dic[2])
                if c != 0:
                    dic[1] = max(c+i, dic[1])
                if b != 0:
                    dic[0] = max(b+i, dic[0] )
        return dic[0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dp = [[-math.inf]*3 for _ in nums]
        dp[0][nums[0]%3] = nums[0]
        for i, n in enumerate(nums[1:], start=1):
            dp[i][n%3] = n
            for j in range(3):
                dp[i][j] = max(dp[i][j], dp[i-1][j], n+dp[i-1][(j-n%3)%3])
        ans = dp[-1][0]
        return ans if ans > 0 else 0


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        f = [[0] * 3 for i in range(len(nums))]
        f[0][nums[0] % 3] = nums[0]
        for i in range(1, len(nums)):
            for j in range(3):
                include = f[i-1][(j + 3 - nums[i] %3) % 3] + nums[i]
                if include % 3 == j:
                    f[i][j] = max(f[i-1][j], include)
                else:
                    f[i][j] = f[i-1][j]
        return f[-1][0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        # dp 0/1 problem
        dp = [ [0] * len(nums) for _ in range(3)]
        
        for i, n in enumerate(nums):
            if i == 0:
                dp[n%3][0] = n
            
            else:
                for rem in range(3):
                    if dp[rem][i-1] % 3 == rem:
                        # choose / don't choose
                        dp[(n+rem)%3][i] = max(dp[rem][i-1] + n, dp[(n+rem)%3][i-1]) 
                    else:
                        dp[(n+rem)%3][i] = dp[(n+rem)%3][i-1]
                    

        return dp[0][-1] if dp[0][-1] != float('-inf') else 0
 



class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dp = [0 for i in range(3)]
        for num in nums:
            tmp = dp[:]
            for remainder in range(3):
                dp[(tmp[remainder]+num)%3] = max(dp[(tmp[remainder]+num)%3], tmp[remainder] + num)
            # print('num, dp', num, dp)
        return dp[0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1 and nums[0] % 3:
            return 0

        sum_ = sum(nums)
        mod_ = sum_ % 3
        if not mod_:
            return sum_

        vals = {False: self.min_two([n for n in nums if n % 3 == 3 - mod_]),
                True: [min([n for n in nums if n % 3 == mod_])]}

        if vals[True] and (len(vals[False]) <= 1 or vals[True][0] < sum(vals[False])):
            return sum_ - vals[True][0]

        elif len(vals[False]) == 2:
            return sum_ - sum(vals[False])
        return 0



    def min_two(self, l):
        if not l:
            return []
        idx = [i for i in range(len(l))]
        out = [min(idx, key = lambda i: l[i])]
        idx.pop(out[0])
        if idx:
            out.append(min(idx, key = lambda i: l[i]))

        return [l[i] for i in out]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dic = {0: 0}
        
        for num in nums:
            dic_new = {}
            
            for prev_remain, prev_sum in list(dic.items()):
                remain = (prev_remain + num) % 3
                dic_new[remain] = max(num + prev_sum, dic.get(remain, 0))
                
            for remain, sum_val in list(dic_new.items()):
                dic[remain] = max(sum_val, dic.get(remain, 0))

        return dic[0]


class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        states = [0, float('-inf'), float('-inf')]
        
        for n in nums:
            old = states[:]
            for i in range(3):
                states[(i + n) % 3] = max(old[(i + n) % 3], old[i] + n)
        
        return states[0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[0 for i in range(3)] for i in range(n + 1)]
        dp[0] = [0, -1e18, -1e18]
        
        for i, v in enumerate(nums):
            for k in range(3):
                dp[i + 1][k] = max( dp[i][k], v + dp[i][(k - (v % 3) + 3) % 3])
        
        return dp[n][0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dic = {0: 0}
        
        for n in nums:
            dic_new = {}
            
            for i, s in dic.items():
                r = (i + n) % 3
                dic_new[r] = max(n + s, dic.get(r, 0))
                
            for i, s in dic_new.items():
                dic[i] = max(s, dic.get(i, 0))
                        
        return dic.get(0, 0)

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        zero = one = two = 0
        for n in nums:
            nz, no, nt = zero + n, one + n, two + n
            zero = max(zero, nz if nz%3 == 0 else 0, no if no%3 == 0 else 0, nt if nt%3 == 0 else 0)
            one = max(one, nz if nz%3 == 1 else 0, no if no%3 == 1 else 0, nt if nt%3 == 1 else 0)
            two = max(two, nz if nz%3 == 2 else 0, no if no%3 == 2 else 0, nt if nt%3 == 2 else 0)
            # print(zero, one, two)
        
        return zero

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        
        @lru_cache(None)
        def recurse(i,pos):
            if pos<0:
                if i==0:
                    return 0
                return -10000000
                
            temp = max(nums[pos]+recurse((i+nums[pos])%3,pos-1),recurse((i)%3,pos-1))
        
            #print(i,pos,temp)
            return temp
        
        return recurse(0,len(nums)-1)

def maxsum(a, k):
    dp =[float('-inf') if a[0]%k!=x else a[0] for x in range(k)]
    for i in range(1, len(a)):
        new = [0 for x in range(k)]
        for j in range(k):
            rem=a[i]%k
            index = (k-rem+j)%k
            new[j] = max(dp[j], dp[index]+a[i], a[i] if a[i]%k==j else float('-inf'))
        dp = new

    return 0 if dp[0] ==float('-inf') else dp[0]

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        return maxsum(nums, 3)

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        @lru_cache(None)
        def dfs(index, remainder):
            if index == len(nums):
                if remainder == 0:
                    return 0
                else:
                    return -float('inf')
            
            
            new_remainder = (nums[index] + remainder) % 3
            choose = dfs(index + 1, new_remainder) + nums[index]
            no_choose = dfs(index + 1, remainder)
            
            return max(choose, no_choose)
        
        return dfs(0,0)