# 1262. Greatest Sum Divisible by Three

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).

# Solution

Approach 1: DP -- knapsack, with values modulo-ed.

# Code (Python)

Approach 1:

class Solution:
    def maxSumDivThree0(self, nums: List[int]) -> int:
        # idea: knapsack, time O(N*sum(nums)) -- TLE
        # can_sum[i][v]: can sum to v with first i numbers
        # can_sum[i][v] = can_sum[i-1][v] or can_sum[i-1][v-nums[i-1]]
        can_sum = [[True] + [False] * sum(nums) for _ in range(len(nums) + 1)]
        for i in range(1, len(can_sum)):
            for v in range(len(can_sum[0])):
                can_sum[i][v] = can_sum[i-1][v] or can_sum[i-1][v-nums[i-1]]
        for v in range(sum(nums), -1, -1):
            if v % 3 == 0 and can_sum[-1][v]:
                return v
        return 0
    
    def maxSumDivThree(self, nums: List[int]) -> int:
        # knapsack, but with only 3 values: % == 0, 1, 2. Time O(N).
        # Caveat: can reduce the dimensions to 2 rows, but now 1 row, because the modulo wraps around
        max_sum = [[0] * 3 for _ in range(len(nums))]
        max_sum[0][nums[0] % 3] = nums[0]
        for i in range(len(nums)):
            num = nums[i]
            for v in (0, 1, 2):
                index = (max_sum[i-1][(v - num) % 3] + num) % 3
                if index == v:
                    max_sum[i][v] = max(max_sum[i-1][v], max_sum[i-1][(v - num) % 3] + num)
                else:
                    max_sum[i][v] = max_sum[i-1][v]
        return max_sum[-1][0]

# Code (C++)

Approach 1:

Approach 2: