Tags: "leetcode", "dynamic-programming", access_time 2-min read

Greatest Sum Divisible by Three

Created: February 15, 2020 by [lek-tin]

Last updated: February 15, 2020

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. 1 <= nums.length <= 4 * 10^4
2. 1 <= nums[i] <= 10^4

Solution

dp[0][i]: greatest sum that is %3 == 0 from nums[0...i]
dp[1][i]: greatest sum that is %3 == 1 from nums[0...i]
dp[2][i]: greatest sum that is %3 == 2 from nums[0...i]

import math

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        N = len(nums)
        dp = [ [0 for j in range(N+1)] for i in range(3) ]
        dp[1][0] = -math.inf
        dp[2][0] = -math.inf

        for i in range(1, n+1):
            num = nums[i-1]
            if num % 3 == 0:
                dp[0][i] = max(dp[0][i-1], dp[0][i-1] + num)
                dp[1][i] = max(dp[1][i-1], dp[1][i-1] + num)
                dp[2][i] = max(dp[2][i-1], dp[2][i-1] + num)
            if num % 3 == 1:
                dp[0][i] = max(dp[0][i-1], dp[2][i-1] + num)
                dp[1][i] = max(dp[1][i-1], dp[0][i-1] + num)
                dp[2][i] = max(dp[2][i-1], dp[1][i-1] + num)
            if num % 3 == 2:
                dp[0][i] = max(dp[0][i-1], dp[1][i-1] + num)
                dp[1][i] = max(dp[1][i-1], dp[2][i-1] + num)
                dp[2][i] = max(dp[2][i-1], dp[0][i-1] + num)

        return dp[0][n]