Skip to content

1388. Greatest Sum Divisible By Three

Array Dynamic Programming Greedy Sorting

Problem - Greatest Sum Divisible By Three

Medium

Given an integer array nums, return 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 * 104
  • 1 <= nums[i] <= 104

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[float('-inf')] * 3 for _ in range(n + 1)]
        dp[0][0] = 0

        for i, val in enumerate(nums, 1):
            for j in range(3):
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][(j - val) % 3] + val)

        return dp[-1][0]

Submission Stats:

  • Runtime: 155 ms (18.93%)
  • Memory: 28.1 MB (17.16%)